POJ - 1474 :Video Surveillance (半平面交-求核)

pro:顺时针给定多边形,问是否可以放一个监控,可以监控到所有地方,即问是否存在多边形的核。 此题如果两点在同一边界上(且没有被隔段),也可以相互看到。

sol:求多边形是否有核。先给直线按角度排序,然后增量法即可,复杂度O(NlogN)。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const double eps=1e-;
struct point{
double x,y;
point(){}
point(double xx,double yy):x(xx),y(yy){}
};
struct line{
point a;//起点
point p;//起点到终点的向量
double angle;
};
double dot(point a,point b){ return a.x*b.x+a.y*b.y;}
double det(point a,point b){ return a.x*b.y-a.y*b.x;}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator +(point A,point B){return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B){return point(A.x-B.x,A.y-B.y);}
double getangle(point a){ return atan2(a.y,a.x);}
double getangle(line a){ return getangle(a.p);}
point llintersect(line A,line B)
{
point C=A.a-B.a;
double t=det(C,B.p)/det(B.p,A.p);
return A.a+A.p*t;
}
point s[maxn]; line t[maxn],q[maxn]; int head,tail;
bool cmp(line a,line b){
double A=getangle(a),B=getangle(b);
point t=(b.a+b.p)-a.a;
if(fabs(A-B)<eps) return det(a.p,t)>=0.0;
return A<B;
}
bool onright(line P,line a,line b)
{
point o=llintersect(a,b);
point Q=o-P.a;
return det(Q,P.p)>; //如果同一直线上不能相互看到,则>=0
}
bool halfplaneintersect(int N)
{
s[N+]=s[];
rep(i,,N) t[i].a=s[i],t[i].p=s[i+]-s[i];
sort(t+,t+N+,cmp);
int tot=;
rep(i,,N-) {
if(fabs(getangle(t[i])-getangle(t[i+]))>eps)
t[++tot]=t[i];
}
t[++tot]=t[N]; head=tail=;
rep(i,,tot){
while(tail>head+&&onright(t[i],q[tail],q[tail-])) tail--;
while(tail>head+&&onright(t[i],q[head+],q[head+])) head++;
q[++tail]=t[i];
}
while(tail>head+&&onright(t[head+],q[tail],q[tail-])) tail--;return tail-head>;
}
void solve(int C,int N)
{
for(int i=N;i>=;i--) scanf("%lf%lf",&s[i].x,&s[i].y);
printf("Floor #%d\n",C);
if(halfplaneintersect(N)) puts("Surveillance is possible.\n");
else puts("Surveillance is impossible.\n");
}
int main()
{
int N,C=;
while(~scanf("%d",&N)&&N) solve(++C,N);
return ;
}
上一篇:【建项目】eclipse maven建立多模块工程


下一篇:vue+ajax+bootstrap+python实现增删改