学步园

题目：题目链接

题意：就是每次给出一个坐标，然后相对于上一个坐标这个点到宝藏的 距离是靠近（hotter）还是远离（colder），

还是不变（same）；

分析：这样的话，等于每次走一次就确定一个半平面区域，也就是从这个点到另一个点的中垂线然后分割成的半平面，

求可能存在的面积。

改了一下午，怎么都不对，改来改去，煞笔了，模版的一个小地方敲错了。

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
const double eps = 1e-8;
const int maxn = 100;
using namespace std;

struct point
{
    double x, y;
} p[maxn], q[maxn], devil[maxn];
point p1, p2;

double ok;

int n, m;
int s;
//判-1, 0, 1
double judge(double x)
{
    if(fabs(x) < eps)
        return 0;
    else if(x > eps)
        return 1;
    else
        return -1;
}
//求交点
void jiao(point x, point y, double a, double b, double c)
{
    double u = fabs(a*x.x + b*x.y + c);
    double v = fabs(a*y.x + b*y.y + c);
    q[++s].x = (x.x*v + y.x*u)/(u+v);
    q[s].y = (x.y*v + y.y*u)/(u+v);
}

//半平面交求切多边形
void cut(double a, double b, double c)
{
    s = 0;
    for(int i = 1; i <= m; ++i)
    {
        if(judge((a*p[i].x + b*p[i].y + c)*ok) >= 0)
            q[++s] = p[i];
        else
        {
            if(judge((a*p[i-1].x + b*p[i-1].y + c) * ok) > 0)
                jiao(p[i-1], p[i], a, b, c);
            if(judge((a*p[i+1].x + b*p[i+1].y + c) * ok) > 0)
                jiao(p[i], p[i+1], a, b, c);
        }
    }
    //更新剩余的多边形
    for(int i = 1; i <= s; ++i)
        p[i] = q[i];
    p[0] = p[s];
    p[s+1] = p[1] ;
    m = s;
}

void init()
{
    n = m = 4;
    devil[1].x = 0;
    devil[1].y = 0;
    devil[2].x = 10;
    devil[2].y = 0;
    devil[3].x = 10;
    devil[3].y = 10;
    devil[4].x = 0;
    devil[4].y = 10;
    devil[5] = devil[1];
    devil[0] = devil[5];
    for(int i = 1; i <= 4; ++i)
        p[i] = devil[i];
    p[0] = p[n];
    p[n+1] = p[1];
}
double AREA()
{
    double area = 0.0;
    for(int i = 1; i <= m; i++)
        area += (p[i].x*p[i+1].y - p[i].y*p[i+1].x);
    return area/2.0;
}
//求线a*x+b*y+c = 0
void LINEZL(point p0, point p1, point p2)
{
    double a, b, c;
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p2.x*p1.y - p2.y*p1.x;
    ok = a*p0.x + b*p0.y + c;
    cut(a, b, c);
}
int main()
{
    p1.x = p1.y = 0;
    char op[15];
    int flag = 1;
    init();
    while(~scanf("%lf%lf%s", &p2.x, &p2.y, op))
    {
        point t1, t2;
        t1.x = (p1.x + p2.x)/2;
        t1.y = (p1.y + p2.y)/2;
        t2.x = t1.x + p1.y - p2.y;
        t2.y = t1.y + p2.x - p1.x;
        if(strcmp(op, "Same") == 0 || !flag)
        {
            printf("0.00\n");
            flag = 0;
            continue;
        }
        if(strcmp(op, "Colder") == 0)
            LINEZL(p1, t1, t2);
        else if(strcmp(op, "Hotter") == 0)
            LINEZL(p2, t1, t2);
        printf("%.2lf\n", fabs(AREA()));
        if(fabs(AREA()) < eps)
            flag = 0;
        p1 = p2;
    }
    return 0;
}