poj 2540 Hotter Colder(선형 계획 가능 영역)

Hotter Colder
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 1836
 
Accepted: 764
Description
The children's game Hotter Colder is played as follows. Player A leaves the room while player B hides an object somewhere in the room. Player A re-enters at position (0,0) and then visits various other positions about the room. When player A visits a new position, player B announces "Hotter"if this position is closer to the object than the previous position; player B announces "Colder"if it is farther and "Same"if it is the same distance.
Input
Input consists of up to 50 lines, each containing an x,y coordinate pair followed by "Hotter", "Colder", or "Same". Each pair represents a position within the room, which may be assumed to be a square with opposite corners at (0,0) and (10,10).
Output
For each line of input print a line giving the total area of the region in which the object may have been placed, to 2 decimal places. If there is no such region, output 0.00.
Sample Input

10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

Sample Output

50.00
37.50
12.50
0.00

Source
Waterloo local 2001.01.27
제목:http://poj.org/problem?id=2540
제목: 두 사람이 물건을 숨기고, 하나는 숨기고, 하나는 찾고, 집의 대소사 0, 0에서 10, 10, 10의 정사각형을 찾고, 0, 0부터 찾고, 매번 이전보다 가까운지 멀었는지 알려준다. 매번 있을 수 있는 구역의 크기를 묻는다.
분석: 매번 전번보다 가깝거나 멀거나 같거나 같으면 면적은 반드시 0이다. 그러면 남은 것은 같지 않다. 앞뒤 두 점을 따라 수직 평분선을 하고 평분선의 방정식은 멀어지면 0보다 작게 하고 가까워지면 반대로 한다. 이렇게 하면 구선형 계획의 실행 가능한 구역 크기로 전환할 수 있다. 반평면으로 제출할 수 있다. 방에 있는 네 개의 반평면을 더하면 가까스로 1Y를 다시 낸다. 이 몇 번은 정밀도 문제를 T_T
코드:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mm=111;
const double eps=1e-8;
typedef double diy;
struct point
{
    diy x,y;
    point(){}
    point(diy _x,diy _y):x(_x),y(_y){}
}g[mm];
point Vector(point s,point t)
{
    return point(t.x-s.x,t.y-s.y);
}
diy CrossProduct(point P,point Q)
{
    return P.x*Q.y-P.y*Q.x;
}
diy MultiCross(point P,point Q,point R)
{
    return CrossProduct(Vector(Q,P),Vector(Q,R));
}
struct halfPlane
{
    point s,t;
    diy angle;
    halfPlane(){}
    halfPlane(point _s,point _t){s=_s,t=_t,angle=atan2(t.y-s.y,t.x-s.x);}
}hp[mm],q[mm];
point Intersection(halfPlane P,halfPlane Q)
{
    diy a1=CrossProduct(Vector(P.s,Q.t),Vector(P.s,Q.s));
    diy a2=CrossProduct(Vector(P.t,Q.s),Vector(P.t,Q.t));
    return point((P.s.x*a2+P.t.x*a1)/(a1+a2),(P.s.y*a2+P.t.y*a1)/(a1+a2));
}
halfPlane MakeHP(diy a,diy b,diy c)
{
    if(fabs(a)<eps)
        return halfPlane(point(b<0?-1:1,-c/b),point(b<0?1:-1,-c/b));
    if(fabs(b)<eps)
        return halfPlane(point(-c/a,a<0?1:-1),point(-c/a,a<0?-1:1));
    if(b<0)return halfPlane(point(0,-c/b),point(1,-(a+c)/b));
    return halfPlane(point(1,-(a+c)/b),point(0,-c/b));
}
bool IsParallel(halfPlane P,halfPlane Q)
{
    return fabs(CrossProduct(Vector(P.s,P.t),Vector(Q.s,Q.t)))<eps;
}
bool cmp(halfPlane P,halfPlane Q)
{
    if(fabs(P.angle-Q.angle)<eps)
        return MultiCross(P.s,P.t,Q.s)>0;
    return P.angle<Q.angle;
}
void HalfPlaneIntersect(int &n,int &m)
{
    sort(hp,hp+n,cmp);
    int i,l=0,r=1;
    for(m=i=1;i<n;++i)
        if(hp[i].angle-hp[i-1].angle>eps)hp[m++]=hp[i];
    n=m,m=0;
    q[0]=hp[0],q[1]=hp[1];
    for(i=2;i<n;++i)
    {
        if(IsParallel(q[r],q[r-1])||IsParallel(q[l],q[l+1]))break;
        while(l<r&&MultiCross(hp[i].s,hp[i].t,Intersection(q[r],q[r-1]))>0)--r;
        while(l<r&&MultiCross(hp[i].s,hp[i].t,Intersection(q[l],q[l+1]))>0)++l;
        q[++r]=hp[i];
    }
    while(l<r&&MultiCross(q[l].s,q[l].t,Intersection(q[r],q[r-1]))>0)--r;
    while(l<r&&MultiCross(q[r].s,q[r].t,Intersection(q[l],q[l+1]))>0)++l;
    q[++r]=q[l];
    for(i=l;i<r;++i)
        g[m++]=Intersection(q[i],q[i+1]);
}
int main()
{
    char sta[9];
    diy sx=0,sy=0,tx,ty,a,b,c,ans;
    int i,n=0,m,flag=1;
    hp[n++]=halfPlane(point(0,0),point(10,0));
    hp[n++]=halfPlane(point(10,0),point(10,10));
    hp[n++]=halfPlane(point(10,10),point(0,10));
    hp[n++]=halfPlane(point(0,10),point(0,0));
    while(~scanf("%lf%lf%s",&tx,&ty,sta))
    {
        a=sx-tx;
        b=sy-ty;
        c=-(a*(sx+tx)+b*(sy+ty))/2;
        if(sta[0]=='H')hp[n++]=MakeHP(a,b,c);
        if(sta[0]=='C')hp[n++]=MakeHP(-a,-b,-c);
        if(sta[0]=='S')flag=0;
        ans=0;
        if(flag)
        {
            HalfPlaneIntersect(n,m);
            if(m>2)
            {
                g[m]=g[0];
                for(i=0;i<m;++i)
                    ans+=CrossProduct(g[i],g[i+1]);
            }
        }
        if(ans<0)ans=-ans;
        printf("%.2lf
",ans/2);
        sx=tx,sy=ty;
    }
    return 0;
}