首页 > 代码库 > poj3335 半平面交模版
poj3335 半平面交模版
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef double dd; #define N 200 struct P{ dd x,y; P(dd a=0,dd b=0){ x=a,y=b; } P operator+(P a){ return P(x+a.x,y+a.y); } P operator-(P a){ return P(x-a.x,y-a.y); } P operator*(dd a){ return P(x*a,y*a); } void out(){ cout<<x<<" "<<y<<" "; } }z[N]; struct ply{ int siz; P a[N]; ply(){ siz=0; } }; dd mul(P x,P y,P z){ return (y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y); } P jiao(P a,P b,P c,P d){ dd a1=mul(c,a,b),a2=mul(d,b,a); return c+(d-c)*(a1/(a1+a2)); } int cas,n; ply add(ply x,P a,P b){ ply res; for(int i=0;i<x.siz;i++){ P t1=x.a[i]; P t2=x.a[(i+1)%x.siz]; dd c=mul(a,t1,b); dd d=mul(a,t2,b); if(c>=0)res.a[res.siz++]=t1; if(c*d<0){ res.a[res.siz++]=jiao(t1,t2,a,b); } } return res; } bool ok(){ ply now; now.siz=4; now.a[0]=P(-1e10,-1e10); now.a[1]=P(-1e10,1e10); now.a[2]=P(1e10,1e10); now.a[3]=P(1e10,-1e10); for(int i=0;i<n;i++){ now=add(now,z[i],z[(i+1)%n]); if(!now.siz)return 0; } return 1; } int main(){ scanf("%d",&cas); while(cas--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&z[i].x,&z[i].y); } if(ok()){ printf("YES\n"); }else{ printf("NO\n"); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。