POJ3335
半平面交裸题
//poj3335
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 50110;
using namespace std;
int sgn(double x) {
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
else return 1;
}
struct Point {
double x,y;
Point(){}Point(double _x,double _y){x=_x;y=_y;}
void input() {
scanf("%lf%lf",&x,&y);
}
bool operator == (Point b) const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
bool operator < (Point b) const{
return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
}
Point operator - (const Point &b) const {
return Point(x-b.x,y-b.y);
}
double operator ^ (const Point &b) const {
return x*b.y - y*b.x;
}
double operator * (const Point &b) const {
return x*b.x + y*b.y;
}
Point operator * (const double &k) const {
return Point(x*k,y*k);
}
Point operator / (const double &k) const {
return Point(x/k,y/k);
}
Point operator + (const Point &b) const {
return Point(x+b.x,y+b.y);
}
double len() {
return hypot(x,y);
}
double len2() {
return x*x+y*y;
}
double distance(Point p) {
return hypot(x-p.x,y-p.y);
}
};
struct Line {
Point s,e;
Line(){}
Line(Point _s,Point _e){s=_s;e=_e;}
Line(double a ,double b ,double c) {
if(sgn(a)==0) {
s = Point(0,-c/b);
e = Point(1,-c/b);
}
else if(sgn(b)==0) {
s = Point(-c/a,0);
e = Point(-c/a,1);
}
else {
s = Point(0,-c/b);
e = Point(1,(-c-a)/b);
}
}
double length(){
return s.distance(e);
}
bool parallel(Line v) {
return sgn((e-s)^(v.e-v.s))==0;
}
double dispointtoline(Point p) {
return fabs((p-s)^(e-s))/length();
}
Point lineprog(Point p) {
return s + ( ((e-s)*((e-s)*(p-s)))/(e-s).len2() );
}
Point crosspoint(Line v) {
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
int pointseg(Point p) { // update: 点在线段上
return sgn((p-s)^(e-s)) == 0 && min(s.x,e.x) <= p.x && p.x <= max(s.x,e.x) && min(s.y,e.y) <= p.y && p.y <= max(s.y,e.y);
}
};
struct polygon {
int n;
Point p[maxp];
Line l[maxp];
void getline() {
for(int i=0;i<n;++i)
l[i] = Line(p[i],p[(i+1)%n]);
}
void input(int _n) {
n = _n;
rep(i,0,n-1) p[i].input();
}
};
struct halfplane: public Line {
double angle;
halfplane(){}
halfplane(Point _s,Point _e) {
s = _s; e = _e;
}
halfplane(Line v) {
s = v.s; e = v.e;
}
void output() {
printf("s: (%f,%f)
",s.x,s.y);
printf("e: (%f,%f)
",e.x,e.y);
}
void calcangle() {
angle = atan2(e.y-s.y,e.x-s.x);
}
bool operator < (const halfplane &b)const {
return angle < b.angle;
}
};
struct halfplanes {
int n;
halfplane hp[maxp];
Point p[maxp];
int que[maxp];
int st,ed;
void push(halfplane tmp) {
hp[n++] = tmp;
}
void unique() {
int m = 1;
for(int i=1;i<n;++i) {
if(sgn(hp[i].angle-hp[i-1].angle)!=0)
hp[m++] = hp[i];
else if(sgn( (hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s) ) > 0)
hp[m-1] = hp[i];
}
n = m;
}
bool halfplaneinsert() {
for(int i=0;i<n;++i) hp[i].calcangle();
sort(hp,hp+n);
unique();
que[st=0] = 0;
que[ed=1] = 1;
p[1] = hp[0].crosspoint(hp[1]);
for(int i=2;i<n;++i) {
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
que[++ed] = i;
if(hp[i].parallel(hp[que[ed-1]])) return false;
p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
}
while(st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
while(st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
if(st+1>=ed) return false;
return true;
}
void getconvex(polygon &con) {
p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
con.n = ed-st+1;
for(int j=st,i=0;j<=ed;++i,++j)
con.p[i] = p[j];
}
}A;
polygon P;
int n,T;
bool usd[maxp];
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
P.input(n);
P.getline();
A.n = 0;
rep(i,0,n-1) {
Line tl = P.l[i];
swap(tl.s,tl.e);
A.push(halfplane(tl));
}
if(A.halfplaneinsert()) puts("YES");
else puts("NO");
}
return 0;
}