1 #include<vector>  2 #include<list>  3 #include<map>  4 #include<set>  5 #include<deque>  6 #include<queue>  7 #include<stack>  8 #include<bitset>  9 #include<algorithm> 10 #include<functional> 11 #include<numeric> 12 #include<utility> 13 #include<iostream> 14 #include<sstream> 15 #include<iomanip> 16 #include<cstdio> 17 #include<cmath> 18 #include<cstdlib> 19 #include<cctype> 20 #include<string> 21 #include<cstring> 22 #include<cstdio> 23 #include<cmath> 24 #include<cstdlib> 25 #include<ctime> 26 #include<climits> 27 #include<complex> 28 #define mp make_pair 29 #define pb push_back 30 using namespace std; 31 const double eps=1e-8;//精度 32 const double pi=acos(-1.0);//π 33 const double inf=1e20;//无穷大 34 const int maxp=1111;//最大点数 35 /* 36     判断d是否在精度内等于0 37 */ 38 int dblcmp(double d) 39 { 40     if (fabs(d)<eps)return 0; 41     return d>eps?1:-1; 42 } 43  44  45 bool dcmp(double x) 46 { 47     return (fabs(x)<eps); 48 } 49  50 /* 51     求x的平方 52 */ 53 inline double sqr(double x){return x*x;} 54 /* 55     点/向量 56 */ 57 struct point 58 { 59     double x,y; 60     point(){} 61     point(double _x,double _y):x(_x),y(_y){}; 62     //读入一个点 63     void input() 64     { 65         scanf("%lf%lf",&x,&y); 66     } 67     //输出一个点 68     void output() 69     { 70         printf("%.2f %.2f\n",x,y); 71     } 72     //判断两点是否相等 73     bool operator==(point a)const 74     { 75         return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0; 76     } 77     //判断两点大小 78     bool operator<(point a)const 79     { 80         return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x<a.x; 81     } 82     //点到源点的距离/向量的长度 83     double len() 84     { 85         return hypot(x,y); 86     } 87     //点到源点距离的平方 88     double len2() 89     { 90         return x*x+y*y; 91     } 92     //两点间的距离 93     double distance(point p) 94     { 95         return hypot(x-p.x,y-p.y); 96     } 97     //向量加 98     point add(point p) 99     {100         return point(x+p.x,y+p.y);101     }102     //向量减103     point sub(point p)104     {105         return point(x-p.x,y-p.y);106     }107     //向量乘108     point mul(double b)109     {110         return point(x*b,y*b);111     }112     //向量除113     point div(double b)114     {115         return point(x/b,y/b);116     }117     //点乘118     double dot(point p)119     {120         return x*p.x+y*p.y;121     }122     //叉乘123     double det(point p)124     {125         return x*p.y-y*p.x;126     }127     //XXXXXXX128     double rad(point a,point b)129     {130         point p=*this;131         return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));132     }133     //截取长度r134     point trunc(double r)135     {136         double l=len();137         if (!dblcmp(l))return *this;138         r/=l;139         return point(x*r,y*r);140     }141     //左转90度142     point rotleft()143     {144         return point(-y,x);145     }146     //右转90度147     point rotright()148     {149         return point(y,-x);150     }151     //绕点p逆时针旋转angle角度152     point rotate(point p,double angle)153     {154         point v=this->sub(p);155         double c=cos(angle),s=sin(angle);156         return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);157     }158 };159 160 bool point_cmp(point a,point b)161 {162     return ((dcmp(a.x-b.x))&&(dcmp(a.y-b.y)));163 }164 165 /*166     线段/直线167 */168 struct line169 {170     point a,b;171     line(){}172     line(point _a,point _b)173     {174         a=_a;175         b=_b;176     }177     //判断线段相等178     bool operator==(line v)179     {180         return (a==v.a)&&(b==v.b);181     }182     //点p做倾斜角为angle的射线183     line(point p,double angle)184     {185         a=p;186         if (dblcmp(angle-pi/2)==0)187         {188             b=a.add(point(0,1));189         }190         else191         {192             b=a.add(point(1,tan(angle)));193         }194     }195     //直线一般式ax+by+c=0196     line(double _a,double _b,double _c)197     {198         if (dblcmp(_a)==0)199         {200             a=point(0,-_c/_b);201             b=point(1,-_c/_b);202         }203         else if (dblcmp(_b)==0)204         {205             a=point(-_c/_a,0);206             b=point(-_c/_a,1);207         }208         else209         {210             a=point(0,-_c/_b);211             b=point(1,(-_c-_a)/_b);212         }213     }214     //读入一个线段215     void input()216     {217         a.input();218         b.input();219     }220     //校准线段两点221     void adjust()222     {223         if (b<a)swap(a,b);224     }225     //线段长度226     double length()227     {228         return a.distance(b);229     }230     //直线倾斜角 0<=angle<180231     double angle()232     {233         double k=atan2(b.y-a.y,b.x-a.x);234         if (dblcmp(k)<0)k+=pi;235         if (dblcmp(k-pi)==0)k-=pi;236         return k;237     }238     //点和线段关系239     //1 在逆时针240     //2 在顺时针241     //3 平行242     int relation(point p)243     {244         int c=dblcmp(p.sub(a).det(b.sub(a)));245         if (c<0)return 1;246         if (c>0)return 2;247         return 3;248     }249     //点是否在线段上250     bool pointonseg(point p)251     {252         //if ((p==a) || (p==b))  return true;253         return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;254     }255     //两线是否平行256     bool parallel(line v)257     {258         return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;259     }260     //线段和线段关系261     //0 不相交262     //1 非规范相交263     //2 规范相交264     int segcrossseg(line v)265     {266         int d1=dblcmp(b.sub(a).det(v.a.sub(a)));267         int d2=dblcmp(b.sub(a).det(v.b.sub(a)));268         int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));269         int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));270         if ((d1^d2)==-2&&(d3^d4)==-2)return 2;271         return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||272                 d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||273                 d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||274                 d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);275     }276     //线段和直线v关系277     int linecrossseg(line v)//*this seg v line278     {279         int d1=dblcmp(b.sub(a).det(v.a.sub(a)));280         int d2=dblcmp(b.sub(a).det(v.b.sub(a)));281         if ((d1^d2)==-2)return 2;282         return (d1==0||d2==0);283     }284     //直线和直线关系285     //0 平行286     //1 重合287     //2 相交288     int linecrossline(line v)289     {290         if ((*this).parallel(v))291         {292             return v.relation(a)==3;293         }294         return 2;295     }296     //求两线交点297     point crosspoint(line v)298     {299         if ((point_cmp(a,v.a))||(point_cmp(a,v.b)))     return a;300         if ((point_cmp(b,v.a))||(point_cmp(b,v.b)))     return b;301         double a1=v.b.sub(v.a).det(a.sub(v.a));302         double a2=v.b.sub(v.a).det(b.sub(v.a));303         return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));304     }305 306     //点p到直线的距离307     double dispointtoline(point p)308     {309         return fabs(p.sub(a).det(b.sub(a)))/length();310     }311     //点p到线段的距离312     double dispointtoseg(point p)313     {314         if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)315         {316             return min(p.distance(a),p.distance(b));317         }318         return dispointtoline(p);319     }320     //XXXXXXXX321     point lineprog(point p)322     {323         return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));324     }325     //点p关于直线的对称点326     point symmetrypoint(point p)327     {328         point q=lineprog(p);329         return point(2*q.x-p.x,2*q.y-p.y);330     }331 };332 333 334 struct point P[1000];335 struct line  L[1000];336 int n;337 int CASE=0;338 339 int main()340 {341     //freopen("in.txt","r",stdin);342 343     while (cin>>n)344     {345         if (n==0)   break;346         {347             CASE++;348             n--;349             for (int i=1;i<=n+1;i++)350             {351                 scanf("%lf%lf",&P[i].x,&P[i].y);352                 if (i>=2)353                     L[i-1]=line(point(P[i-1].x,P[i-1].y),point(P[i].x,P[i].y));354             }355             //L[1..n]:line      P[1..n]:point   P[1]==P[n+1]356 357             vector<point> POINT;358             POINT.clear();359 360             int pcount=0;       //the number of points361             for (int i=1;i<n;i++)362                 for (int j=i+1;j<=n;j++)363                 {364                     if (L[i].segcrossseg(L[j])!=0)365                     {366                         point tm=L[i].crosspoint(L[j]);367                         //printf("P:   %.3f   %.3f\n",tm.x,tm.y);368                         bool Find=false;369                         for (vector<point>::iterator it=POINT.begin();it!=POINT.end();it++)370                         {371                             point tp=*it;372                             if ((dcmp(tp.x-tm.x))&&(dcmp(tp.y-tm.y)))373                                 Find=true;374                         }375                         if (!Find)376                         {377                             pcount++;378                             POINT.push_back(tm);379                         }380                     }381                 }382 383             for (vector<point>::iterator it=POINT.begin();it!=POINT.end();it++)384             {385                 point tp=*it;386                 //printf("%.5f %.5f\n",tp.x,tp.y);387             }388 389             int lcount=0;390             for (int i=1;i<=n;i++)391             {392                 line tm=L[i];393                 int tmp=0;394                 for (vector<point>::iterator it=POINT.begin();it!=POINT.end();it++)395                 {396                     point tp=*it;397                     if (tm.pointonseg(tp))398                         tmp++;399                 }400                 lcount=lcount+(tmp-1);401             }402 403             //cout<<pcount<<"   "<<lcount<<endl;404             //cout<<2+lcount-pcount<<endl;405             //Case 1: There are 2 pieces.406             int ans=2+lcount-pcount;407             //if (ans<0)  ans=2;408             printf("Case %d: There are %d pieces.\n",CASE,ans);409         }410     }411 412 413     return 0;414 }