# Poj Solution 2284

```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;
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;

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;
}

```
This entry was posted in poj. Bookmark the permalink.