Video Surveillance - POJ 1474(判断是否存在内核)

题目大意:询问是否在家里装一个监视器就可以监控所有的角落。

分析:赤裸裸的判断多边形内核题目。

代码如下:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std; const int MAXN = ;
const int oo = 1e9+;
const double EPS = 1e-; int Sign(double t)
{
if(t > EPS)
return ;
if(fabs(t) < EPS)
return ;
return -;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x),y(y){}
Point operator - (const Point &t)const{
return Point(x-t.x, y-t.y);
}
double operator ^(const Point &t)const{
return x*t.y - y*t.x;
} }p[MAXN], in[MAXN];
struct Segment
{
Point S, E;
double a, b, c;
Segment(Point S=, Point E=):S(S), E(E){
a = S.y - E.y;
b = E.x - S.x;
c = E.x*S.y - S.x*E.y;
}
Point crossNode(const Segment &t)const{
Point res; res.x = (c*t.b-t.c*b) / (a*t.b-t.a*b);
res.y = (c*t.a-t.c*a) / (b*t.a-t.b*a); return res;
}
int Mul(const Point &t)
{///用叉积判断方向
return Sign((E-S)^(t-S));
}
};
int CutPoly(Segment L, int N)
{
Point tmp[MAXN];
int cnt = ; for(int i=; i<=N; i++)
{
if(L.Mul(in[i]) <= )
tmp[++cnt] = in[i];
else
{
if(L.Mul(in[i-]) < )///求出交点
tmp[++cnt] = L.crossNode(Segment(in[i-],in[i]));
if(L.Mul(in[i+]) < )
tmp[++cnt] = L.crossNode(Segment(in[i],in[i+]));
}
} for(int i=; i<=cnt; i++)
in[i] = tmp[i];
in[] = in[cnt], in[cnt+] = in[]; return cnt;
} int main()
{
int N, t=; while(scanf("%d", &N) != EOF && N)
{
int M;
double s=; for(int i=; i<=N; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
in[i] = p[i];
if(i != )
s += p[i].x*p[i-].y - p[i].y*p[i-].x;
}
s += p[].x*p[N].y - p[].y*p[N].x;
if(s < )
{
for(int i=; i<=N/; i++)
{
swap(p[i], p[N-i+]);
swap(in[i], in[N-i+]);
}
} in[] = p[] = p[N];
in[N+] = p[N+] = p[];
M = N; for(int i=; i<=N; i++)
M = CutPoly(Segment(p[i],p[i+]), M); printf("Floor #%d\n", t++);
if(M > )
printf("Surveillance is possible.\n\n");
else
printf("Surveillance is impossible.\n\n");
} return ;
}
上一篇:POJ 3280 Cheapest Palindrome(DP 回文变形)


下一篇:vmware 8下ubuntu 13.04安装vmware tools