这题水的真不易。。300多行 累死了 对着数据查错啊
枚举每个边上的点到源点 是否中间隔着别的边 每条边划分500份就够了 注意一下与源点在一条直线上的边不算
几何 啊，，好繁琐 参考各种模版。。
1 /* 2 ID: shangca2 3 LANG: C++ 4 TASK: fence4 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm> 10 #include<stdlib.h> 11 #include<cmath> 12 using namespace std; 13 typedef struct pointt 14 { 15 double x,y; 16 pointt(double x=0,double y=0):x(x),y(y){} 17 }vec; 18 struct node 19 { 20 int x1,y1,x2,y2,o1,o2; 21 }po[210]; 22 vec p,pp[210],q[4010]; 23 int e,n; 24 vec operator + (vec a,vec b){return vec(a.x+b.x,a.y+b.y);} 25 vec operator - (pointt a,pointt b){return vec(a.x-b.x,a.y-b.y);} 26 vec operator * (vec a,double b){return vec(a.x*b,a.y*b);} 27 vec operator / (vec a,double b){return vec(a.x/b,a.y/b);} 28 bool operator < (const pointt &a,const pointt &b) 29 { 30 return a.x<b.x||(a.x==b.x&&a.y<b.y); 31 } 32 const double eps = 1e-15; 33 int dcmp(double x) 34 { 35 if(fabs(x)<eps) return 0; 36 else return x<0?-1:1; 37 } 38 bool operator == (const pointt &a,const pointt &b) 39 { 40 return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; 41 } 42 double dot(vec a,vec b) 43 { 44 return a.x*b.x+a.y*b.y; 45 } 46 double cross(vec a,vec b) 47 { 48 return a.x*b.y-a.y*b.x; 49 } 50 bool segprointer(pointt a1,pointt a2,pointt b1,pointt b2) 51 { 52 double c1 = cross(a2-a1,b1-a1),c2 = cross(a2-a1,b2-a1), 53 c3 = cross(b2-b1,a1-b1),c4 = cross(b2-b1,a2-b1); 54 return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0; 55 } 56 bool cmp(node a,node b) 57 { 58 if(a.o2==b.o2) 59 return a.o1<b.o1; 60 return a.o2<b.o2; 61 } 62 int judge(int i,int j) 63 { 64 int g; 65 66 for(g = 1; g <= n ; g++) 67 { 68 if(g==i) 69 continue; 70 if(segprointer(q[j],p,pp[g],pp[g+1])) 71 break; 72 } 73 if(g==n+1) 74 { 75 e++; 76 if(i==n) 77 { 78 po[e].x1 = pp[i+1].x; 79 po[e].y1 = pp[i+1].y; 80 po[e].x2 = pp[i].x; 81 po[e].y2 = pp[i].y; 82 po[e].o1 = 1; 83 po[e].o2 = i; 84 } 85 else 86 { 87 po[e].o1 = i; 88 po[e].o2 = i+1; 89 po[e].x1 = pp[i].x; 90 po[e].y1 = pp[i].y; 91 po[e].x2 = pp[i+1].x; 92 po[e].y2 = pp[i+1].y; 93 } 94 return 1; 95 } 96 return 0; 97 } 98 double xmult(vec p1,vec p2,vec p3) 99 { 100 return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y); 101 } 102 int dots(vec p1,vec p2,vec p3) 103 { 104 return dcmp(xmult(p1,p2,p3)); 105 } 106 int main() 107 { 108 freopen("fence4.in","r",stdin); 109 freopen("fence4.out","w",stdout); 110 int i,j,o,g; 111 cin>>n; 112 cin>>p.x>>p.y; 113 for(i = 1 ;i <= n ; i++) 114 cin>>pp[i].x>>pp[i].y; 115 pp[n+1] = pp[1]; 116 for(i = 3; i <= n ; i++) 117 { 118 for(j = 1; j <= i-3 ; j++) 119 { 120 if(i==n&&j==1) 121 continue; 122 if(segprointer(pp[i],pp[i+1],pp[j],pp[j+1])) 123 { 124 puts("NOFENCE"); 125 return 0; 126 } 127 } 128 } 129 vec no; 130 for(i = 1; i <= n ; i++) 131 { 132 if(!dots(p,pp[i],pp[i+1])) 133 continue; 134 o = 0; 135 int fo=0; 136 if(pp[i+1].x==pp[i].x) 137 { 138 double x1 = pp[i].x; 139 double y1; 140 if(pp[i].y<pp[i+1].y) 141 { 142 double xx = (pp[i+1].y-pp[i].y)/300.0; 143 y1 = pp[i].y+xx; 144 while(y1<pp[i+1].y) 145 { 146 o++; 147 q[o].x = x1; 148 q[o].y = y1; 149 if(judge(i,o)) 150 { 151 fo = 1; 152 break; 153 } 154 y1+=xx; 155 } 156 } 157 else 158 { 159 double xx = (pp[i].y-pp[i+1].y)/300.0; 160 y1 = pp[i].y-xx; 161 while(y1>pp[i+1].y) 162 { 163 o++; 164 q[o].x = x1; 165 q[o].y = y1; 166 if(judge(i,o)) 167 { 168 fo = 1; 169 break; 170 } 171 y1-=xx; 172 } 173 } 174 } 175 else if(pp[i+1].y==pp[i].y) 176 { 177 178 double x1; 179 double y1=pp[i].y; 180 if(pp[i+1].x>pp[i].x) 181 { 182 double xx = (pp[i+1].x-pp[i].x)/500.0; 183 x1 = pp[i].x+xx; 184 while(x1<pp[i+1].x) 185 { 186 o++; 187 q[o].x = x1; 188 q[o].y = y1; 189 if(judge(i,o)) 190 { 191 fo = 1; 192 break; 193 } 194 x1+=xx; 195 } 196 } 197 else 198 { 199 double xx = (pp[i].x-pp[i+1].x)/500.0; 200 x1 = pp[i].x-xx; 201 while(x1>pp[i+1].x) 202 { 203 o++; 204 q[o].x = x1; 205 q[o].y = y1; 206 if(judge(i,o)) 207 { 208 fo = 1; 209 if(i==7) 210 cout<<x1<<" "<<y1<<endl; 211 break; 212 } 213 x1-=xx; 214 } 215 } 216 } 217 else 218 { 219 double d = (pp[i+1].y-pp[i].y)/(pp[i+1].x-pp[i].x); 220 double k1,x1,y1; 221 double xx = fabs((pp[i+1].x-pp[i].x)/500.0); 222 k1 = 1.0*fabs(d); 223 if(pp[i+1].x>pp[i].x&&pp[i+1].y>pp[i].y) 224 { 225 x1 = pp[i].x+0.1; 226 y1 = pp[i].y+0.1*k1; 227 while(x1<pp[i+1].x&&y1<pp[i+1].y) 228 { 229 o++; 230 q[o].x = x1; 231 q[o].y = y1; 232 if(judge(i,o)) 233 { 234 fo = 1; 235 break; 236 } 237 x1+=xx; 238 y1+=xx*k1; 239 } 240 } 241 else if(pp[i+1].x<pp[i].x&&pp[i+1].y>pp[i].y) 242 { 243 x1 = pp[i].x-0.1; 244 y1 = pp[i].y+0.1*k1; 245 while(x1>pp[i+1].x&&y1<pp[i+1].y) 246 { 247 o++; 248 q[o].x = x1; 249 q[o].y = y1; 250 if(judge(i,o)) 251 { 252 fo = 1; 253 break; 254 } 255 x1-=xx; 256 y1+=xx*k1; 257 } 258 } 259 else if(pp[i+1].x<pp[i].x&&pp[i+1].y<pp[i].y) 260 { 261 x1 = pp[i].x-0.1; 262 y1 = pp[i].y-0.1*k1; 263 while(x1>pp[i+1].x&&y1>pp[i+1].y) 264 { 265 o++; 266 q[o].x = x1; 267 q[o].y = y1; 268 if(judge(i,o)) 269 { 270 fo = 1; 271 break; 272 } 273 x1-=xx; 274 y1-=xx*k1; 275 } 276 } 277 else 278 { 279 x1 = pp[i].x+0.1; 280 y1 = pp[i].y-0.1*k1; 281 while(x1<pp[i+1].x&&y1>pp[i+1].y) 282 { 283 o++; 284 q[o].x = x1; 285 q[o].y = y1; 286 if(judge(i,o)) 287 { 288 fo = 1; 289 break; 290 } 291 x1+=xx; 292 y1-=xx*k1; 293 } 294 } 295 } 296 } 297 sort(po+1,po+e+1,cmp); 298 cout<<e<<endl; 299 for(i = 1; i <= e ; i++) 300 { 301 cout<<po[i].x1<<" "<<po[i].y1<<" "<<po[i].x2<<" "<<po[i].y2<<endl; 302 } 303 return 0; 304 }