POJ3335 POJ3130 POJ1474 [半平面交]

终于写出自己的半平面交模板了.......

加入交点的地方用了直线线段相交判定

三个题一样,能从任何地方看到就是多边形的内核

只不过一个顺时针一个逆时针(给出一个多边形的两种方式啦),反正那个CutPolygon是切掉左面只要穿参数时换一下就好了

第三题卡输出啊啊啊啊啊

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N=;
const double INF=1e5;
const double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
} inline int sgn(double x){
if(abs(x)<eps) return ;
else return x<?-:;
} struct Vector{
double x,y;
Vector(double a=,double b=):x(a),y(b){}
bool operator <(const Vector &a)const{
return sgn(x-a.x)<||(sgn(x-a.x)==&&sgn(y-a.y)<);
}
void print(char c){printf("%c %lf %lf\n",c,x,y);}
};
typedef Vector Point;
Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==&&sgn(a.y-b.y)==;}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} double Len(Vector a){return sqrt(Dot(a,a));} double DisTL(Point p,Point a,Point b){
Vector v1=b-a,v2=p-a;
return abs(Cross(v1,v2)/Len(v1));
}
struct Line{
Point s,t;
Line(){}
Line(Point a,Point b):s(a),t(b){}
};
bool isLSI(Line l1,Line l2){
Vector v=l1.t-l1.s,u=l2.s-l1.s,w=l2.t-l1.s;
return sgn(Cross(v,u))!=sgn(Cross(v,w));
}
Point LI(Line a,Line b){
Vector v=a.s-b.s,v1=a.t-a.s,v2=b.t-b.s;
double t=Cross(v2,v)/Cross(v1,v2);
return a.s+v1*t;
}
void iniPolygon(Point p[],int &n,double inf){
n=;
p[++n]=Point(-inf,-inf);
p[++n]=Point(inf,-inf);
p[++n]=Point(inf,inf);
p[++n]=Point(-inf,inf);
}
Point t[N];int tn;
void CutPolygon(Point p[],int &n,Point a,Point b){//get the left of a->b
tn=;
Point c,d,e;
for(int i=;i<=n;i++){
c=p[i],d=p[i%n+];
if(sgn(Cross(b-a,c-a))>=) t[++tn]=c;
if(isLSI(Line(a,b),Line(c,d))){
e=LI(Line(a,b),Line(c,d));//e.print('e');
t[++tn]=e;
}
}
n=tn;for(int i=;i<=n;i++)p[i]=t[i];
} int n,m;
Point p[N],q[N];
int main(int argc, const char * argv[]) {
int cas=;
while(true){
n=read();if(n==) break;
iniPolygon(q,m,INF);
for(int i=;i<=n;i++) p[i].x=read(),p[i].y=read();
for(int i=;i<=n;i++) CutPolygon(q,m,p[i%n+],p[i]);//,printf("%d\n",m);
printf("Floor #%d\n",++cas);
if(m) puts("Surveillance is possible.\n");
else puts("Surveillance is impossible.\n");
}
}
上一篇:QA笑话----杂思


下一篇:BZOJ 2527 [POI2011]MET-Meteors (整体二分+树状数组)