http://poj.org/problem?id=2540
题意:给你每次行走的路径,而且告诉你每次离一个点光源是远了还是近了,要求每次光源可能存在的位置的面积。
思路:如果出现"same",说明光源在中垂线上,面积为0,否则我们考虑远了或者近了,实际上就是在路径中两点连成直线的中垂线就是半平面直线,近了在这条直线的远侧,远了在这条直线的近侧。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
const double Pi=acos(-);
bool flag=;
int tot;
struct Point{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
}a[],p[];
struct Line{
Point s,e;
double slop;
Line(){}
Line(Point s0,Point e0):s(s0),e(e0){}
}l[],L[],c[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
double operator *(Point p1,Point p2){
return p1.x*p2.y-p1.y*p2.x;
}
Point operator +(Point p1,Point p2){
return Point(p1.x+p2.x,p1.y+p2.y);
}
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}
Point operator /(Point p1,double x){
return Point(p1.x/x,p1.y/x);
}
bool cmp(Line p1,Line p2){
if (p1.slop!=p2.slop) return p1.slop<p2.slop;
else return (p1.e-p1.s)*(p2.e-p1.s)<=;
}
Point turn(Point p1,double ang){
double Cos=cos(ang),Sin=sin(ang);
double x=p1.x*Cos-p1.y*Sin;
double y=p1.x*Sin+p1.y*Cos;
return Point(x,y);
}
Point inter(Line p1,Line p2){
double t1=(p2.e-p1.s)*(p1.e-p1.s);
double t2=(p1.e-p1.s)*(p2.s-p1.s);
double k=(t2)/(t1+t2);
double x=(p2.e.x-p2.s.x)*k+p2.s.x;
double y=(p2.e.y-p2.s.y)*k+p2.s.y;
return Point(x,y);
}
bool jud(Line p1,Line p2,Line p3){
Point p=inter(p1,p2);
return (p-p3.s)*(p3.e-p3.s)>;
}
double query(){
std::sort(l+,l++tot,cmp);
if (!cmp(l[tot-],l[tot])) return 0.0;
int cnt=;L[]=l[];
for (int i=;i<=tot;i++)
if (l[i].slop!=l[i-].slop) L[++cnt]=l[i];
int ll=,rr=;c[ll]=L[];c[rr]=L[];
for (int i=;i<=cnt;i++){
while (ll<rr&&jud(c[rr],c[rr-],L[i])) rr--;
while (ll<rr&&jud(c[ll],c[ll+],L[i])) ll++;
c[++rr]=L[i];
}
while (ll<rr&&jud(c[rr],c[rr-],c[ll])) rr--;
while (ll<rr&&jud(c[ll],c[ll+],c[rr])) ll++;
if (rr-ll+<) {flag=;return 0.00;}
double ans=;
cnt=;
c[rr+]=c[ll];
for (int i=ll;i<=rr;i++)
a[++cnt]=inter(c[i],c[i+]);
a[cnt+]=a[];
for (int i=;i<=cnt;i++)
ans+=a[i]*a[i+];
ans/=2.0;
return fabs(ans);
}
int main(){
p[]=Point(,);
char s[];double x,y;flag=;int i=;
l[++tot].s=Point(,);l[tot].e=Point(,);l[tot].slop=atan2(l[tot].e.y-l[tot].s.y,l[tot].e.x-l[tot].s.x);
l[++tot].s=Point(,);l[tot].e=Point(,);l[tot].slop=atan2(l[tot].e.y-l[tot].s.y,l[tot].e.x-l[tot].s.x);
l[++tot].s=Point(,);l[tot].e=Point(,);l[tot].slop=atan2(l[tot].e.y-l[tot].s.y,l[tot].e.x-l[tot].s.x);
l[++tot].s=Point(,);l[tot].e=Point(,);l[tot].slop=atan2(l[tot].e.y-l[tot].s.y,l[tot].e.x-l[tot].s.x);
while (scanf("%lf%lf",&p[i].x,&p[i].y)!=EOF){
scanf("%s",s+);
if (s[]=='S') flag=;
if (flag){puts("0.00");continue;}
if (s[]=='C'){
Point mid=(p[i]+p[i-])/2.0;
l[++tot].e=mid+turn(p[i]-p[i-],Pi/2.0);
l[tot].s=mid;
}else{
Point mid=(p[i]+p[i-])/2.0;
l[++tot].e=mid+turn(p[i]-p[i-],Pi*3.0/2.0);
l[tot].s=mid;
}
l[tot].slop=atan2(l[tot].e.y-l[tot].s.y,l[tot].e.x-l[tot].s.x);
printf("%.2f\n",query());
i++;
}
}