小凸想跑步-半平面交

题目大意

在一个凸包里,找一个点$p$,使得该点与$\{k,k+1,k\in(1,n-1)\}$组成的三角形面积大于和$\{0,1\}$组成的三角形面积.

解析

首先,我们考虑点的取值范围.
必定在凸包内以及凸包的边界上.
用线性规划半平面交表示即为:每个边所在直线的左半边区域交集.
再考虑,三角形面积关系:
$\overrightarrow{(x_1-x,y_1-y)}\times\overrightarrow{(x_0-x,y_0-y)}\leq\overrightarrow{(x_{k+1}-x,y_{k+1}-y)}\times\overrightarrow{(x_k-x,y_k-y)}$
然后一堆化简整理之后:
$(y_1-y_0-y_{k+1}+y_k)x+(x_0-x_1-x_k+x_{k+1})y+(x_1y_0-x_0y_1-x_{k+1}y_k+x_ky_{k+1})\ge 0$
一个形如$ax+by+c\ge 0$的式子就写出来了.
对于一个形如上述的式子,该直线的向量为$(b,-a)$,根据这个就可以用两点式表示直线.
然后对于$k\in\{1,n-1\}$的点,都求一次直线.
再与上面的直线求半平面交.得到符合条件的解即可.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;
const double pi = acos(-1.0);
const double inf = 1e100;
const double eps = 1e-12;

typedef struct point vec; //向量vec
struct point { //点的基本数据结构
    double x, y;
    double poe;
    point(double _x = 0, double _y = 0)
        : x(_x)
        , y(_y)
    {
    }
    point operator*(const point& i_T) const
    {
        return point(x * i_T.x, y * i_T.y);
    }
    point operator*(double u) const
    {
        return point(x * u, y * u);
    }
    bool operator==(const point& i_T) const
    {
        return x == i_T.x && y == i_T.y;
    }
    point operator/(double u) const
    {
        return point(x / u, y / u);
    }
    point operator+(const point& i_T)
    {
        return point(x + i_T.x, y + i_T.y);
    }
    point operator-(const point& i_T)
    {
        return point(x - i_T.x, y - i_T.y);
    }
    friend bool operator<(point a, point b)
    {
        return a.y == b.y ? a.x < b.x : a.y < b.y;
    }
    void atn2()
    {
        poe = atan2(y, x);
    }
    friend ostream& operator<<(ostream& out, point& a)
    {
        //cout << a.x << ' ' << a.y;
        printf("%.2f %.2f", a.x, a.y);
        return out;
    }
    friend istream& operator>>(istream& in, point& a)
    {
        scanf("%lf%lf", &a.x, &a.y);
        return in;
    }
};
typedef struct Line Segment; //线段Segment
struct Line { //直线
    point a, b;
    double poe;
    Line(point _a = point(), point _b = point())
        : a(_a)
        , b(_b)
    {
    }
    bool operator==(const Line& i_T) const
    {
        return a == i_T.a && b == i_T.b;
    }
    friend istream& operator>>(istream& in, Line& a)
    {
        cin >> a.a >> a.b;
        return in;
    }
    friend ostream& operator<<(ostream& out, Line& a)
    {
        out << a.a << ' ' << a.b;
        return out;
    }
    void atn2()
    {
        poe = atan2(b.y - a.y, b.x - a.x);
    }
};
double chaji(vec A, vec B) //求向量叉积
{
    return A.x * B.y - A.y * B.x; // 正为A->B左旋
}
int zhengfu(double d) //判断正负
{
    if (fabs(d) < eps)
        return 0;
    if (d > 0)
        return 1;
    return -1;
}
int bijiao(double x, double y)
{
    if (fabs(x - y) < eps)
        return 0;
    if (x > y)
        return 1;
    return -1;
}
bool cmp(Line l1, Line l2) //半平面交的极角排序
{
    return bijiao(l1.poe, l2.poe) == 0 ? zhengfu(chaji(l1.b - l1.a, l2.b - l1.a)) > 0 : l1.poe < l2.poe;
}
point p[MAXN];
Line l[MAXN], q[MAXN];
point zhixian_zhixian_jiaodian(Line l1, Line l2) //两直线交点
{
    double t = ((l1.a.x - l2.a.x) * (l2.a.y - l2.b.y) - (l1.a.y - l2.a.y) * (l2.a.x - l2.b.x)) / ((l1.a.x - l1.b.x) * (l2.a.y - l2.b.y) - (l1.a.y - l1.b.y) * (l2.a.x - l2.b.x));
    return l1.a + (l1.b - l1.a) * t;
}

double duobianxingmianji(point po[], int num) //多边形面积
{
    double ans = 0;
    po[num + 1] = po[1];
    for (int i = 1; i <= num; i++)
        ans += chaji(po[i], po[i + 1]);
    ans = fabs(ans) * 0.5;
    return ans;
}
double solve(int head, int tail)
{
    int num = 0;
    q[tail + 1] = q[head];
    for (int i = head; i <= tail; i++)
        p[++num] = zhixian_zhixian_jiaodian(q[i], q[i + 1]);
    if (num < 3)
        return 0;
    return duobianxingmianji(p, num);
}
bool check(Line a, Line b, Line c) //判断a,b交点是否在c的右边
{
    point o = zhixian_zhixian_jiaodian(a, b);
    return zhengfu(chaji(c.b - c.a, o - c.a)) < 0;
}

void banpingmian_jiao(int& head, int& tail, Line L[], int t) //求半平面交
{
    sort(L + 1, L + t + 1, cmp);
    head = 1, tail = 0;
    int cnt = 0;
    for (int i = 1; i < t; i++) {
        if (bijiao(L[i].poe, L[i + 1].poe) == 0)
            continue;
        L[++cnt] = L[i]; //因为排过序，即使极角相同，后面的也比前面的优
    }
    L[++cnt] = L[t];

    for (int i = 1; i <= cnt; i++) {
        while (head < tail && check(q[tail - 1], q[tail], L[i]))
            tail--;
        while (head < tail && check(q[head + 1], q[head], L[i]))
            head++;
        q[++tail] = L[i];
    }

    while (head < tail && check(q[tail - 1], q[tail], q[head]))
        tail--;
    while (head < tail && check(q[head + 1], q[head], q[tail]))
        head++;
}
int main()
{
    int n;
    cin >> n;

    double ans=0;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    p[n + 1] = p[1];
    ans=duobianxingmianji(p,n);

    for (int i = 1; i <= n; i++){
        l[i] = Line(p[i], p[i + 1]);
        l[i].atn2();
    }
    int t = n;
    for (int i = 2; i <= n; i++) {
        double a = (p[2] - p[1] - p[i + 1] + p[i]).y;
        double b = (p[1] - p[2] - p[i] + p[i + 1]).x;
        double c = p[2].x * p[1].y - p[1].x * p[2].y - p[i + 1].x * p[i].y + p[i].x * p[i + 1].y;
        if (zhengfu(a) == zhengfu(b) && zhengfu(a) == 0)
            continue;
        if (zhengfu(a)!=0) {
            l[++t] = Line(point(-c / a, 0), point(-c / a + b, -a));
        } else if (zhengfu(b)!=0) {
            l[++t] = Line(point(0, -c / b), point(b, -c / b - a));
        }
        l[t].atn2();
    }
    int head, tail;
    banpingmian_jiao(head, tail, l, t);

    printf("%.4f\n", solve(head, tail)/ans);

    return 0;
}