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