半平面类的模板。。

用n个半平面去切割一个多边形。。最后求多边形面积。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const double EPS = 1e-6;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    void input(){scanf("%lf%lf", &x, &y);}
    double getDis(Point &rhs)
    {
        double xx = x - rhs.x;
        xx *= xx;
        double yy = y - rhs.y;
        yy *= yy;
        return sqrt(xx + yy);
    }
    double x, y;
};
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
Point operator +(Point lhs, Point rhs){return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
Point operator -(Point lhs, Point rhs){return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);}
Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);}

bool isCross(Point &a, Point &b, Point &c, Point &d)
{
    if(min(a.x, b.x) <= max(c.x, d.x) &&
        min(a.y, b.y) <= max(c.y, d.y) &&
        min(c.x, d.x) <= max(a.x, b.x) &&
        min(c.y, d.y) <= max(a.y, b.y))
    {
        double u, v, w, z;
        u = (c - a) ^ (b - a);
        v = (d - a) ^ (b - a);
        w = (a - c) ^ (d - c);
        z = (b - c) ^ (d - c);
        if(u * v <= EPS && w * z <= EPS && fabs((a - b) ^ (c - d)) > EPS) return true;
    }
    return false;
}
Point getIntersect(Point &a, Point &b, Point &c, Point &d)
{
    double D = (a - b) ^ (c - d);
    double a1 = b.y - a.y, a2 = d.y - c.y;
    double b1 = a.x - b.x, b2 = c.x - d.x;
    double c1 = a ^ (b - a), c2 = c ^ (d - c);
    Point ret = Point((b2 * c1 - b1 * c2) / D, (a1 * c2 - a2 * c1) / D);
    return ret;
}

double getPolygonArea(vector<Point> &point)
{
    double ret = 0.0;
    int n = point.size();
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        ret += point[nxt] ^ point[i];
    }
    return ret / 2.0;
}

struct HalfPlane
{
    double a, b, c;//Ax + By + C = 0
    bool isDownSide;//下方半平面 = true（B < 0）

    HalfPlane(Point p, Point q, bool _isDownSide)
    {
        a = p.y - q.y;
        b = q.x - p.x;
        c = p ^ q;
        isDownSide = _isDownSide;
    }

    HalfPlane() {}

    HalfPlane(double _a, double _b, double _c, bool _isDownSide = true):
         a(_a), b(_b), c(_c), isDownSide(_isDownSide) {}
    double calc(Point &t)
    {
        return t.x * a + t.y * b + c;
    }

    Point getIntersect(Point &a, Point &b)//半平面与直线的交点
    {
        Point ret;
        double t1 = calc(a), t2 = calc(b);
        ret.x = (t2 * a.x - t1 * b.x) / (t2 - t1);
        ret.y = (t2 * a.y - t1 * b.y) / (t2 - t1);
        return ret;
    }

    bool isInHalfPlane(Point &t)//一个点是否在半平面内
    {
        double temp = calc(t);
        if(isDownSide) return temp <= -EPS;
        else return temp >= EPS;
    }
};

HalfPlane h;
vector<Point> point, out;
Point pre, now;

void getCut(vector<Point> &a, HalfPlane &h, vector<Point> &out)
{
    int n = a.size();
    out.clear();
    for(int i = 0; i < n; ++i)
    {
        if(h.isInHalfPlane(a[i])) out.push_back(a[i]);
        else
        {
            int pre = (i + n - 1) % n;
            if(h.isInHalfPlane(a[pre])) out.push_back(h.getIntersect(a[pre], a[i]));
            int nxt = (i + 1) % n;
            if(h.isInHalfPlane(a[nxt])) out.push_back(h.getIntersect(a[i], a[nxt]));
        }
    }
}

void insertHalfPlane(HalfPlane &h, Point &pre, Point &now, bool choosePre)
{
    double a = now.y - pre.y, b = pre.x - now.x;
    Point mid = (pre + now) / 2;
    swap(a, b);
    b = -b;
    double c = -(a * mid.x + b * mid.y);
    h = HalfPlane(a, b, c);
    // printf("%lf %lf %lf\n", a, b, c);
    double temp;
    if(choosePre) temp = h.calc(pre);
    else temp = h.calc(now);
    if(temp > 0) h.isDownSide = false;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    double x, y;
    char buf[50];
    point.push_back(Point(0, 0));
    point.push_back(Point(10, 0));
    point.push_back(Point(10, 10));
    point.push_back(Point(0, 10));
    pre = Point(0, 0);
    bool empty = false;
    while(scanf("%lf%lf%s", &x, &y, buf) != EOF)
    {
        if(buf[0] == 'S') empty = true;
        if(empty)
        {
            puts("0.00");
            continue;
        }
        now = Point(x, y);
        if(buf[0] == 'C')
        {
            insertHalfPlane(h, pre, now, true);
        }
        else
        {
            insertHalfPlane(h, pre, now, false);
        }
        getCut(point, h, out);
        // for(auto i : out)
        // {
            // printf("%lf %lf\n", i.x, i.y);
        // }
        point = out;
        if(out.size() == 0)
        {
            empty = true;
        }
        printf("%.2lf\n", fabs(getPolygonArea(point)));
        pre = now;
    }
}