USACO3.4.1Closed Fences

Closed Fences

A closed fence in the plane is a set of non-crossing, connected line segments with N corners (3 < N < 200). The corners or vertices are each distinct and are listed in counter-clockwise order in an array {x_i, y_i}, i in (1..N).

Every pair of adjacent vertices defines a side of the fence. Thus {x_i y_i x_i+1 y_i+1} is a side of the fence for all i in (1..N). For our purposes, N+1 = 1, so that the first and last vertices making the fence closed.

Here is a typical closed fence and a point x,y:

                         * x3,y3
                 x5,y5  / \
    x,y *          *   /   \
                  / \ /     \
                 /   *       \
           x6,y6*   x4,y4     \
                |              \
                |               \
           x1,y1*----------------* x2,y2

Write a program which will do the following:

Test an ordered list of vertices {x_i,y_i}, i in (1..N) to see if the array is a valid fence.
Find the set of fence sides that a person (with no height) who is standing in the plane at position (x,y) can "see" when looking at the fence. The location x,y may fall anywhere not on the fence.

A fence side can be seen if there exists a ray that connects (x,y) and any point on the side, and the ray does not intersect any other side of the fence. A side that is parallel to the line of sight is not considered visible. In the figure, above the segments x3,y3-x4,y4; x5,y5-x6,y6; and x6-y6-x1,y1 are visible or partially visible from x,y.

PROGRAM NAME: fence4

INPUT FORMAT

Line 1:	N, the number of corners in the fence
Line 2:	Two space-separated integers, x and y, that are the location of the observer. Both integers will fit into 16 bits.
Line 3-N+2:	A pair of space-separated integers denoting the X,Y location of the corner. The pairs are given in counterclockwise order. Both integers are no larger than 1000 in magnitude.

NOTE: I have added anNew test case #12 for this task. Let me know if you think it's wrong. Rob Be sure to include USACO in your mail subject!

SAMPLE INPUT (file fence4.in)

OUTPUT FORMAT

If the sequence is not a valid fence, the output is a single line containing the word "NOFENCE".

Otherwise, the output is a listing of visible fence segments, one per line, shown as four space-separated integers that represent the two corners. Express the points in the segment by showing first the point that is earlier in the input, then the point that is later. Sort the segments for output by examining the last point and showing first those points that are earlier in the input. Use the same rule on the first of the two points in case of ties.

SAMPLE OUTPUT (file fence4.out)

7
0 0 7 0
5 2 7 5
7 5 5 7
5 7 3 5
-2 7 0 3
0 0 -3 1
0 3 -3 1
题解：为了这个题目，认认真真的看了下黑书。不过发现只会第一问啊。。就是判断两条线段是否规范相交。。。把黑书上讲的叉积和点积的代码基本全抄上去了。。。可以当模板了。。。第二问想N久木有想得出来啊！！！好蛋疼！！！nocow题解也看不懂！！！！智商拙计啊！！！！第二问的代码各种抄袭！！！主要是看了网友疾走考拉的解题报告（代码基本也是抄他的，不过sin函数和cos函数用不了。。头文件用了math.h。。所以又抄袭了另外一位网友的代码，ORZ。不AC这题就不能去做第四章，只能这样了。。。o(╯□╰)o），方法好神奇。。。。也很容易理解。

View Code

  1 /*
  2 ID:spcjv51
  3 PROG:fence4
  4 LANG:C
  5 */
  6 #include<stdio.h>
  7 #include<math.h>
  8 #include<string.h>
  9 #include<stdlib.h>
 10 #define precision 1e-5
 11 #define MAXN 205
 12 #define MAXS 0x7ffffff
 13 typedef struct
 14 {
 15     double x,y;
 16 } Point;
 17 Point p[MAXN],r;
 18 int see[MAXN],n;
 19 double det(double x1,double y1,double x2,double y2)
 20 {
 21     return x1*y2-x2*y1;
 22 }
 23 double dotdet(double x1,double y1,double x2,double y2)
 24 {
 25     return x1*x2+y1*y2;
 26 }
 27 double dot(Point a,Point b,Point c)
 28 {
 29     return dotdet(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
 30 }
 31 double cross(Point a,Point b,Point c)
 32 {
 33     return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
 34 }
 35 int dblcmp(double d)
 36 {
 37     if(fabs(d)<precision)
 38         return 0;
 39     return (d>0?1:-1);
 40 }
 41 double dis(Point a,Point b)
 42 {
 43     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 44 }
 45 int segcross(Point a,Point b,Point c,Point d,Point *p)
 46 {
 47     double s1,s2,s3,s4;
 48     int d1,d2,d3,d4;
 49     d1=dblcmp(s1=cross(a,b,c));
 50     d2=dblcmp(s2=cross(a,b,d));
 51     d3=dblcmp(s3=cross(c,d,a));
 52     d4=dblcmp(s4=cross(c,d,b));
 53     if((d1^d2)==-2&&(d3^d4)==-2)
 54     {
 55         (*p).x=(c.x*s2-d.x*s1)/(s2-s1);
 56         (*p).y=(c.y*s2-d.y*s1)/(s2-s1);
 57         return 1;
 58     }
 59     return 0;
 60 }
 61 void solve(Point s)
 62 {
 63     int i,k;
 64     double min,t;
 65     Point a;
 66     min=MAXS;
 67     s.x+=(s.x-r.x)*100000000;
 68     s.y+=(s.y-r.y)*100000000;
 69     for(i=0; i<n; i++)
 70     {
 71         if(!segcross(s,r,p[i],p[i+1],&a)) continue;
 72         t=dis(a,r);
 73         if(t<min)
 74         {
 75             min=t;
 76             k=i;
 77         }
 78     }
 79     if(min<MAXS) see[k]=1;
 80 
 81 }
 82 void print(Point a,Point b)
 83 {
 84     printf("%.0lf %.0lf %.0lf %.0lf\n",a.x,a.y,b.x,b.y);
 85 }
 86 int main(void)
 87 {
 88     freopen("fence4.in","r",stdin);
 89     freopen("fence4.out","w",stdout);
 90     int i,j,flag,ans;
 91     Point s;
 92     scanf("%d",&n);
 93     memset(see,0,sizeof(see));
 94     scanf("%lf%lf",&r.x,&r.y);
 95     flag=1;
 96     for(i=0; i<n; i++)
 97         scanf("%lf%lf",&p[i].x,&p[i].y);
 98     p[n]=p[0];
 99     for(i=0; i<n; i++)
100         for(j=i+1; j<n; j++)
101             if(segcross(p[i],p[i+1],p[j],p[j+1],&s))
102             {
103                 flag=0;
104                 break;
105             }
106     if(!flag)
107     {
108         printf("NOFENCE\n");
109         return 0;
110     }
111     for(i=0; i<n; i++)
112     {
113         s.x=p[i].x-10.0*precision;
114         s.y=p[i].y-10.0*precision;
115         solve(s);
116         s.x=p[i].x+10.0*precision;
117         s.y=p[i].y+10.0*precision;
118         solve(s);
119     }
120     ans=0;
121     for(i=0;i<n;i++)
122     if(see[i]) ans++;
123     printf("%d\n",ans);
124     for(i=0;i<n-2;i++)
125     if(see[i])
126     print(p[i],p[i+1]);
127     if(see[n-1])
128     print(p[n],p[n-1]);
129     if(see[n-2])
130     print(p[n-2],p[n-1]);
131 
132 return 0;
133 }