就是这一组数据害我WA
88
0 20
1 20
1 19
2 19
2 18
3 18
3 17
4 17
4 16
5 16
5 15
6 15
6 14
7 14
7 13
8 13
8 12
9 12
9 11
10 11
10 10
11 10
11 9
12 9
12 8
13 8
13 7
14 7
14 6
15 6
15 5
16 5
16 4
17 4
17 3
18 3
18 2
19 2
19 1
20 1
20 0
1 0
1 -1
0 -1
0 -20
-1 -20
-1 -19
-2 -19
-2 -18
-3 -18
-3 -17
-4 -17
-4 -16
-5 -16
-5 -15
-6 -15
-6 -14
-7 -14
-7 -13
-8 -13
-8 -12
-9 -12
-9 -11
-10 -11
-10 -10
-11 -10
-11 -9
-12 -9
-12 -8
-13 -8
-13 -7
-14 -7
-14 -6
-15 -6
-15 -5
-16 -5
-16 -4
-17 -4
-17 -3
-18 -3
-18 -2
-19 -2
-19 -1
-20 -1
-20 0
-1 0
-1 1
0 1

答案是possible 但我的程序输出的是impossible
以下是我的程序





#include <iostream>
#include <cmath>
#define Maxn 1005
#define eps 1e-9
using namespace std;

typedef struct TPodouble 
{
	double x;
	double y;
}TPoint;

typedef struct TPolygon
{
	TPoint p[Maxn];
	int n;
};

typedef struct TLine
{
	double a, b, c;
}TLine;

bool same(TPoint p1, TPoint p2)
{
	if(p1.x != p2.x) return false;
	if(p1.y != p2.y) return false;
	return true;
}
 
double multi(TPoint p1, TPoint p2, TPoint p0)
{
    //求矢量[p0, p1], [p0, p2]的叉积
    //p0是顶点 
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    //若结果等于0，则这三点共线
    //若结果大于0，则p0p2在p0p1的逆时针方向
    //若结果小于0，则p0p2在p0p1的顺时针方向 
}

TLine lineFromSegment(TPoint p1, TPoint p2)
{
    //线段所在直线,返回直线方程的三个系统 
    TLine tmp;
    tmp.a = p2.y - p1.y;
    tmp.b = p1.x - p2.x;
    tmp.c = p2.x * p1.y - p1.x * p2.y;
    return tmp;
}

TPoint LineInter(TLine l1, TLine l2)
{
    //求两直线得交点坐标
    TPoint tmp; 
    double a1 = l1.a;
    double b1 = l1.b;
    double c1 = l1.c;
    double a2 = l2.a;
    double b2 = l2.b;
    double c2 = l2.c;
    //注意这里b1 = 0 
    if(fabs(b1) < eps){
        tmp.x = -c1 / a1;  
        tmp.y = (-c2 - a2 * tmp.x) / b2;
    }       
    else{
        tmp.x = (c1 * b2 - b1 * c2) / (b1 * a2 - b2 * a1);
        tmp.y = (-c1 - a1 * tmp.x) / b1;
    }
	return tmp;
}

TPolygon Cut_polygon(TPoint p1,TPoint p2,TPolygon polygon)
{
      TPolygon new_polygon;
      TPoint interp;
      TLine l1,l2;
      int i,j;
      double t1,t2;
      new_polygon.n=0;
      for(i=0;i<polygon.n;i++)
      {
         t1=multi(p2,polygon.p[i],p1);
         t2=multi(p2,polygon.p[i+1],p1);
         if(fabs(t1)<eps||fabs(t2)<eps)
         {
            if(fabs(t1)<eps)new_polygon.p[new_polygon.n++]=polygon.p[i];
            if(fabs(t2)<eps)new_polygon.p[new_polygon.n++]=polygon.p[i+1];
         }
         else if(t1<0&&t2<0)
         {
            new_polygon.p[new_polygon.n++]=polygon.p[i];
            new_polygon.p[new_polygon.n++]=polygon.p[i+1];
         }
         else if(t1*t2<0)
         {
            l1=lineFromSegment(p1,p2);
            l2=lineFromSegment(polygon.p[i],polygon.p[i+1]);
            interp=LineInter(l1,l2);
            if(t1<0)
            {
               new_polygon.p[new_polygon.n++]=polygon.p[i];
               new_polygon.p[new_polygon.n++]=interp;
            }
            else {
                    new_polygon.p[new_polygon.n++]=interp;
                    new_polygon.p[new_polygon.n++]=polygon.p[i+1];
                 }
         }
      }
      polygon.n=0;
      if(new_polygon.n==0)return polygon;
      polygon.p[polygon.n++]=new_polygon.p[0];
      for(i=1;i<new_polygon.n;i++)
         if(!same(new_polygon.p[i],new_polygon.p[i-1]))
            polygon.p[polygon.n++]=new_polygon.p[i];
      if(polygon.n!=1&&same(polygon.p[polygon.n-1],polygon.p[0]))
         polygon.n--;
      polygon.p[polygon.n]=polygon.p[0];
      return polygon;
}

double polygonArea(TPolygon p)
{
    //已知多边形各顶点的坐标，求其面积
    int i, n;
    double area;
    n = p.n;
    area = 0;
    for(i = 1;i <= n;i++){
        area += (p.p[i - 1].x * p.p[i % n].y - p.p[i % n].x * p.p[i - 1].y);
    }  
    area /= 2;
	return area;
}

void ChangeClockwise(TPolygon &polygon)
{
	TPoint tmp;
	int i;
	for(i = 0;i <= (polygon.n - 1) / 2;i++)
    {
		tmp = polygon.p[i];
		polygon.p[i] = polygon.p[polygon.n - 1 - i];
		polygon.p[polygon.n - 1 - i] = tmp;			
	}
}
int main()
{
      int t,i,j,cnt=1;
      TPolygon polygon,new_polygon;
      while(scanf("%d",&polygon.n),polygon.n)
      {
         for(i=0;i<polygon.n;i++)
            scanf("%lf%lf",&polygon.p[i].x,&polygon.p[i].y);
         polygon.p[polygon.n]=polygon.p[0];
         if(polygonArea(polygon)>0)ChangeClockwise(polygon);
         new_polygon=polygon;
         for(i=0;i<polygon.n;i++)
            new_polygon=Cut_polygon(polygon.p[i],polygon.p[i+1],new_polygon);
         printf("Floor #%d\n",cnt++);
         if(new_polygon.n>0)printf("Surveillance is possible.\n\n");
         else printf("Surveillance is impossible.\n\n");
      }
      return 0;
}

• 感谢啊～～你这个数据让我知道1点也不能删 (0) shinejose 2011-05-14 11:50:42
  • Re:感谢啊～～你这个数据让我知道1点也不能删 (3210) 834208094 2012-04-22 06:12:31
    • Re:感谢啊～～你这个数据让我知道1点也不能删 (5971) 834208094 2012-04-24 00:06:09