POJ 1474 Video Surveillance(半平面交)

题目链接

2Y,模版抄错了一点。

 #include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define N 2001
struct point
{
double x,y;
}p[N],pre[N],temp[N];
double a,b,c;
int n,m;
void getline(point x,point y)
{
a = y.y - x.y;
b = x.x - y.x;
c = y.x * x.y - x.x * y.y;
}
point intersect(point x,point y)
{
double u = fabs(a*x.x + b*x.y + c);
double v = fabs(a*y.x + b*y.y + c);
point ans;
ans.x = (x.x*v+y.x*u)/(u+v);
ans.y = (x.y*v+y.y*u)/(u+v);
return ans;
}
void cut()
{
int num = ,i;
for(i = ;i <= m;i ++)
{
if(a*p[i].x + b*p[i].y + c > -eps)
{
temp[++num] = p[i];
}
else
{
if(a*p[i-].x + b*p[i-].y + c > eps)
temp[++num] = intersect(p[i],p[i-]);
if(a*p[i+].x + b*p[i+].y + c > eps)
temp[++num] = intersect(p[i],p[i+]);
}
}
for(i = ;i <= num;i ++)
p[i] = temp[i];
p[] = p[num];
p[num+] = p[];
m = num;
}
void fun()
{
int i;
m = n;
for(i = ;i <= n;i ++)
{
getline(pre[i],pre[i+]);
cut();
}
}
int main()
{
int i,cas = ;
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
for(i = ;i <= n;i ++)
{
scanf("%lf%lf",&pre[i].x,&pre[i].y);
p[i] = pre[i];
}
pre[n+] = pre[];
p[n+] = p[];
p[] = p[n];
fun();
printf("Floor #%d\n",cas ++);
if(m)
printf("Surveillance is possible.\n");
else
printf("Surveillance is impossible.\n");
printf("\n");
}
return ;
}
上一篇:iOS_16_开关控制器_modal_代码方法


下一篇:innerHeight,clientHeight,offsetHeight,scrollWidth等的区别和用法