| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
为什么re#include<cstdio> #include<algorithm> using namespace std; #define N 210 struct xing; struct point { int x,y; point(){} point(int _x,int _y) {x=_x;y=_y;} friend point operator +(const point &p1,const point &p2) { return (point){p1.x+p2.x,p1.y+p2.y}; } friend point operator -(const point &p1,const point &p2) { return (point){p1.x-p2.x,p1.y-p2.y}; } friend point operator *(int k,const point &p) { return (point){p.x*k,p.y*k}; } friend int operator *(const point &p1,const point &p2) { return p1.x*p2.y-p1.y*p2.x; } friend point jiao(const point &p1,const point &v1,const point &p2,const point &v2) { return p1+((p2-p1)*v2)/(v1*v2)*v1; } }x,k; xing *q; struct xing { int n,i; point qa[N],*p=qa+1; int area() { int ans=0; for(i=0;i<n;++i) ans+=p[i]*p[i+1]; return ans; } void init() {scanf("%d",&n); for(i=0;i<n;++i) scanf("%d%d",&p[i].x,&p[i].y); p[n]=p[0]; if(area()<0) reverse(p,p+n+1); } void push(const point &x) { p[n++]=x; } int cha(const point &p) { return k*(p-x); } void cut() { q->n=0; p[-1]=p[n-1];p[n]=p[0]; for (i=0;i<n;++i) { if(cha(p[i])>=0) q->push(p[i]); else { if(cha(p[i-1])>0) q->push(jiao(p[i],p[i-1]-p[i],x,k)); if(cha(p[i+1])>0) q->push(jiao(p[i],p[i+1]-p[i],x,k)); } } (*this)=*q; } }g0,g; int main() { q=new xing; freopen("1.in","r",stdin);freopen("1.out","w",stdout); int tt,i;scanf("%d",&tt); while (tt--) { g0.init();g=g0; for(i=0;i<g0.n;++i) { x=g0.p[i];k=g0.p[i+1]-x; g.cut(); } if(g.n) puts("YES"); else puts("NO"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator