http://poj.org/problem?id=2284
#include"algorithm"
#include"math.h"
#include<iostream>
#include"set"
using namespace std;
struct point
{
double x,y;
};
struct line
{
point a,b;
};
typedef double Type;
inline bool equal(point a,point b)
{
return a.x==b.x&&a.y==b.y;
}
////////////////////////////////////////////////
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}
/////////////////////////////////////////
int jiao(line l1,line l2)
{Type s1=cheng(l1.a,l1.b,l2.a),
s2=cheng(l1.a,l1.b,l2.b),s3,s4;
if(s1*s2>0)return 0;
s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);
if(s3*s4>0)return 0;
if(s1*s2<0&&s3*s4<0)return 1;
if( dcheng(l1.a,l2.a,l2.b)<0
||dcheng(l1.b,l2.a,l2.b)<0
||dcheng(l2.a,l1.a,l1.b)<0
||dcheng(l2.b,l1.a,l1.b)<0)
return 2;
return 0;
}
///////////////////////////////////
point crosspoint(line l1,line l2)
{Type p1=cheng(l2.a,l1.a,l2.b),
p2=cheng(l2.a,l2.b,l1.b);
if(p1+p2==0)return l1.a;
point c;
c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
return c;
}
///////////////////////////////////////////
line edge[400];
int n;
struct cmp
{
bool operator()(point a,point b)const
{
return a.x<b.x||(fabs(a.x-b.x)<1e-8&&a.y<b.y);
}
};
set<point,cmp> p;
set<point,cmp> p_on_l[310];
void init()
{
point p1,p2;line lt;
int i;
p.clear();
for(i=0;i<n;i++)
p_on_l[i].clear();
cin>>p1.x>>p1.y;
for(i=0;i<n;i++)
{
cin>>p2.x>>p2.y;
p.insert(p2);
lt.a=p1;lt.b=p2;
edge[i]=lt;
p_on_l[i].insert(p1);
p_on_l[i].insert(p2);
p1.x=p2.x;
p1.y=p2.y;
}
}
int doit()
{
int i,j;point pt;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(jiao(edge[i],edge[j]))
{
pt=crosspoint(edge[i],edge[j]);
if(p_on_l[i].find(pt)==p_on_l[i].end())p_on_l[i].insert(pt);
if(p_on_l[j].find(pt)==p_on_l[j].end())p_on_l[j].insert(pt);
if(p.find(pt)==p.end())p.insert(pt);
}
int m=0;
for(i=0;i<n;i++)
m+=p_on_l[i].size()-1;
return m+2-p.size();
}
int main()
{
int i=1;
while(1)
{
cin>>n;
if(n==0)break;
n--;
init();
cout<<"Case "<<i++<<": There are "<<doit()<<" pieces."<<endl;
}
return 0;
}