椒江做网站的公司,企业网站托管一年多少钱,网站建设外包合同模板,微信带颜色的公众号题意#xff1a;给出一多边形。判断多边形是否存在一点#xff0c;使得多边形边界上的所有点都能看见该点。 sol#xff1a;在纸上随手画画就可以找出规律#xff1a;按逆时针顺序连接所有点。然后找出这些line的半平面交。 题中给出的点已经按顺时针排好序了#xff0c;所…题意给出一多边形。判断多边形是否存在一点使得多边形边界上的所有点都能看见该点。 sol在纸上随手画画就可以找出规律按逆时针顺序连接所有点。然后找出这些line的半平面交。 题中给出的点已经按顺时针排好序了所以只要倒过来一下就可以了。很简单的模板题。 1 #includevector2 #includelist3 #includemap4 #includeset5 #includedeque6 #includequeue7 #includestack8 #includebitset9 #includealgorithm10 #includefunctional11 #includenumeric12 #includeutility13 #includeiostream14 #includesstream15 #includeiomanip16 #includecstdio17 #includecmath18 #includecstdlib19 #includecctype20 #includestring21 #includecstring22 #includecstdio23 #includecmath24 #includecstdlib25 #includectime26 #includeclimits27 #includecomplex28 #define mp make_pair29 #define pb push_back30 using namespace std;31 const double eps1e-6;32 const double piacos(-1.0);33 const double inf1e20;34 const int maxp1111;35 int dblcmp(double d)36 {37 if (fabs(d)eps)return 0;38 return deps?1:-1;39 }40 inline double sqr(double x){return x*x;}41 struct point42 {43 double x,y;44 point(){}45 point(double _x,double _y):46 x(_x),y(_y){};47 void input()48 {49 scanf(%lf%lf,x,y);50 }51 void output()52 {53 printf(%.2f %.2f\n,x,y);54 }55 bool operator(point a)const56 {57 return dblcmp(a.x-x)0dblcmp(a.y-y)0;58 }59 bool operator(point a)const60 {61 return dblcmp(a.x-x)0?dblcmp(y-a.y)0:xa.x;62 }63 double len()64 {65 return hypot(x,y);66 }67 double len2()68 {69 return x*xy*y;70 }71 double distance(point p)72 {73 return hypot(x-p.x,y-p.y);74 }75 point add(point p)76 {77 return point(xp.x,yp.y);78 }79 point sub(point p)80 {81 return point(x-p.x,y-p.y);82 }83 point mul(double b)84 {85 return point(x*b,y*b);86 }87 point div(double b)88 {89 return point(x/b,y/b);90 }91 double dot(point p)92 {93 return x*p.xy*p.y;94 }95 double det(point p)96 {97 return x*p.y-y*p.x;98 }99 double rad(point a,point b)
100 {
101 point p*this;
102 return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
103 }
104 point trunc(double r)
105 {
106 double llen();
107 if (!dblcmp(l))return *this;
108 r/l;
109 return point(x*r,y*r);
110 }
111 point rotleft()
112 {
113 return point(-y,x);
114 }
115 point rotright()
116 {
117 return point(y,-x);
118 }
119 point rotate(point p,double angle)//绕点p逆时针旋转angle角度
120 {
121 point vthis-sub(p);
122 double ccos(angle),ssin(angle);
123 return point(p.xv.x*c-v.y*s,p.yv.x*sv.y*c);
124 }
125 };
126 struct line
127 {
128 point a,b;
129 line(){}
130 line(point _a,point _b)
131 {
132 a_a;
133 b_b;
134 }
135 bool operator(line v)
136 {
137 return (av.a)(bv.b);
138 }
139 //倾斜角angle
140 line(point p,double angle)
141 {
142 ap;
143 if (dblcmp(angle-pi/2)0)
144 {
145 ba.add(point(0,1));
146 }
147 else
148 {
149 ba.add(point(1,tan(angle)));
150 }
151 }
152 //axbyc0
153 line(double _a,double _b,double _c)
154 {
155 if (dblcmp(_a)0)
156 {
157 apoint(0,-_c/_b);
158 bpoint(1,-_c/_b);
159 }
160 else if (dblcmp(_b)0)
161 {
162 apoint(-_c/_a,0);
163 bpoint(-_c/_a,1);
164 }
165 else
166 {
167 apoint(0,-_c/_b);
168 bpoint(1,(-_c-_a)/_b);
169 }
170 }
171 void input()
172 {
173 a.input();
174 b.input();
175 }
176 void adjust()
177 {
178 if (ba)swap(a,b);
179 }
180 double length()
181 {
182 return a.distance(b);
183 }
184 double angle()//直线倾斜角 0angle180
185 {
186 double katan2(b.y-a.y,b.x-a.x);
187 if (dblcmp(k)0)kpi;
188 if (dblcmp(k-pi)0)k-pi;
189 return k;
190 }
191 //点和线段关系
192 //1 在逆时针
193 //2 在顺时针
194 //3 平行
195 int relation(point p)
196 {
197 int cdblcmp(p.sub(a).det(b.sub(a)));
198 if (c0)return 1;
199 if (c0)return 2;
200 return 3;
201 }
202 bool pointonseg(point p)
203 {
204 return dblcmp(p.sub(a).det(b.sub(a)))0dblcmp(p.sub(a).dot(p.sub(b)))0;
205 }
206 bool parallel(line v)
207 {
208 return dblcmp(b.sub(a).det(v.b.sub(v.a)))0;
209 }
210 //2 规范相交
211 //1 非规范相交
212 //0 不相交
213 int segcrossseg(line v)
214 {
215 int d1dblcmp(b.sub(a).det(v.a.sub(a)));
216 int d2dblcmp(b.sub(a).det(v.b.sub(a)));
217 int d3dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
218 int d4dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
219 if ((d1^d2)-2(d3^d4)-2)return 2;
220 return (d10dblcmp(v.a.sub(a).dot(v.a.sub(b)))0||
221 d20dblcmp(v.b.sub(a).dot(v.b.sub(b)))0||
222 d30dblcmp(a.sub(v.a).dot(a.sub(v.b)))0||
223 d40dblcmp(b.sub(v.a).dot(b.sub(v.b)))0);
224 }
225 int linecrossseg(line v)//*this seg v line
226 {
227 int d1dblcmp(b.sub(a).det(v.a.sub(a)));
228 int d2dblcmp(b.sub(a).det(v.b.sub(a)));
229 if ((d1^d2)-2)return 2;
230 return (d10||d20);
231 }
232 //0 平行
233 //1 重合
234 //2 相交
235 int linecrossline(line v)
236 {
237 if ((*this).parallel(v))
238 {
239 return v.relation(a)3;
240 }
241 return 2;
242 }
243 point crosspoint(line v)
244 {
245 double a1v.b.sub(v.a).det(a.sub(v.a));
246 double a2v.b.sub(v.a).det(b.sub(v.a));
247 return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
248 }
249 double dispointtoline(point p)
250 {
251 return fabs(p.sub(a).det(b.sub(a)))/length();
252 }
253 double dispointtoseg(point p)
254 {
255 if (dblcmp(p.sub(b).dot(a.sub(b)))0||dblcmp(p.sub(a).dot(b.sub(a)))0)
256 {
257 return min(p.distance(a),p.distance(b));
258 }
259 return dispointtoline(p);
260 }
261 point lineprog(point p)
262 {
263 return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
264 }
265 point symmetrypoint(point p)
266 {
267 point qlineprog(p);
268 return point(2*q.x-p.x,2*q.y-p.y);
269 }
270 };
271
272 struct Vector:public point
273 {
274 Vector(){}
275 Vector(double a,double b)
276 {
277 xa; yb;
278 }
279 Vector(point _a,point _b) //a-b
280 {
281 double dx_b.x-_a.x;
282 double dy_b.y-_a.y;
283 xdx; ydy;
284 }
285 Vector(line v)
286 {
287 double dxv.b.x-v.a.x;
288 double dyv.b.y-v.a.y;
289 xdx; ydy;
290 }
291 double length()
292 {
293 return (sqrt(x*xy*y));
294 }
295 Vector Normal()
296 {
297 double Lsqrt(x*xy*y);
298 Vector VansVector(-y/L,x/L);
299 return Vans;
300 }
301 };
302
303 struct halfplane:public line //半平面
304 {
305 double angle;
306 halfplane(){}
307 //表示向量 a-b逆时针(左侧)的半平面
308 halfplane(point _a,point _b)
309 {
310 a_a;
311 b_b;
312 }
313 halfplane(line v)
314 {
315 av.a;
316 bv.b;
317 }
318 void calcangle()
319 {
320 angleatan2(b.y-a.y,b.x-a.x);
321 }
322 bool operator(const halfplane b)const
323 {
324 return angleb.angle;
325 }
326 };
327 struct halfplanes //半平面交
328 {
329 int n;
330 halfplane hp[maxp];
331 point p[maxp];
332 int que[maxp];
333 int st,ed;
334 void push(halfplane tmp)
335 {
336 hp[n]tmp;
337 }
338 void unique()
339 {
340 int m1,i;
341 for (i1;in;i)
342 {
343 if (dblcmp(hp[i].angle-hp[i-1].angle))hp[m]hp[i];
344 else if (dblcmp(hp[m-1].b.sub(hp[m-1].a).det(hp[i].a.sub(hp[m-1].a))0))hp[m-1]hp[i];
345 }
346 nm;
347 }
348 bool halfplaneinsert()
349 {
350 int i;
351 for (i0;in;i)hp[i].calcangle();
352 sort(hp,hpn);
353 unique();
354 que[st0]0;
355 que[ed1]1;
356 p[1]hp[0].crosspoint(hp[1]);
357 for (i2;in;i)
358 {
359 while (steddblcmp((hp[i].b.sub(hp[i].a).det(p[ed].sub(hp[i].a))))0)ed--;
360 while (steddblcmp((hp[i].b.sub(hp[i].a).det(p[st1].sub(hp[i].a))))0)st;
361 que[ed]i;
362 if (hp[i].parallel(hp[que[ed-1]]))return false;
363 p[ed]hp[i].crosspoint(hp[que[ed-1]]);
364 }
365 while (steddblcmp(hp[que[st]].b.sub(hp[que[st]].a).det(p[ed].sub(hp[que[st]].a)))0)ed--;
366 while (steddblcmp(hp[que[ed]].b.sub(hp[que[ed]].a).det(p[st1].sub(hp[que[ed]].a)))0)st;
367 if (st1ed)return false;
368 return true;
369 }
370 /*
371 void getconvex(polygon con)
372 {
373 p[st]hp[que[st]].crosspoint(hp[que[ed]]);
374 con.ned-st1;
375 int jst,i0;
376 for (;jed;i,j)
377 {
378 con.p[i]p[j];
379 }
380 }*/
381 };
382
383 point p[1000];
384 halfplanes TH;
385 int n,T;
386
387 int main()
388 {
389 //freopen(in.txt,r,stdin);
390
391 cinT;
392 while (T--)
393 {
394 cinn;
395 for (int in-1;i0;i--)
396 p[i].input();
397 //p[i]-p[i1]
398
399 TH.n0;
400 for (int i0;in-1;i)
401 TH.push(halfplane(p[i],p[(i1)%n]));
402
403 if (TH.halfplaneinsert())
404 coutYESendl;
405 else coutNOendl;
406 }
407
408 return 0;
409 } View Code 转载于:https://www.cnblogs.com/pdev/p/4277687.html
