【题解】[POI2008]Tro 计算几何 BZOJ – 1132

题目链接_(:з」∠)_

嗯。。。第一次看到这题的时候。。。通篇四个大字

我 不 会 做

真是丢人

暴力做法就是枚举三个点，然后用叉乘算该三角形面积

因为叉乘除了交换律不满足以外别的基本都满足，叉乘是满足分配率的

所以只需要枚举两个点构成的向量 $\vec{ij}$，能与其叉乘为正的那些向量都是与其夹角 $> 0$且 $< \pi$的，因此按关于 $i$的极角排序后 two-points 扫一遍，对于每个 $\vec {ij}$都求与其夹角 $\in (0, \pi)$的那些向量的和，然后和 $\vec {ij}$做叉乘就能算出 $\vec {ij}$的贡献了

复杂度是 $O(n ^ 2 log _ 2 n)$的

因为数据很大所以 double 不够用，得开 long long 或者 long double

#include <bits/stdc++.h>

#define NS (3005)
#define eps (1e-10)

using namespace std;

typedef long double LD;

const LD PI = acos(-1);

struct vec
{
    LD x, y, angle;
    vec() {x = y = 0;}
    vec(LD a, LD b) {x = a, y = b;}
    void input() {scanf("%Lf%Lf", &x, &y);}
    vec operator + (const vec oth) const {return vec(x + oth.x, y + oth.y);}
    vec operator - (const vec oth) const {return vec(x - oth.x, y - oth.y);}
    bool operator < (const vec oth) const {return angle < oth.angle;}
    LD crs(const vec oth) {return x * oth.y - y * oth.x;}
} P[NS];

int n;

LD ans;

int main(int argc, char const* argv[])
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i += 1) P[i].input();
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = i + 1; j <= n; j += 1)
        {
            P[j].angle = atan2(P[j].y - P[i].y, P[j].x - P[i].x);
            if (P[j].angle < 0) P[j].angle += PI * 2;
        }
        P[i].angle = 0, sort(P + i + 1, P + n + 1);
        LD lim = PI; int p = i + 1; vec Q;
        for (int j = i + 1; j <= n; j += 1)
        {
            lim += P[j].angle - P[j - 1].angle;
            while (p <= n && P[p].angle < lim) Q = Q + P[p++] - P[i];
            if (lim >= PI * 2)
            {
                lim -= PI * 2;
                if (p > n) p = i + 1;
                while (p <= n && P[p].angle < lim) Q = Q + P[p++] - P[i];
            }
            ans += (P[j] - P[i]).crs(Q) * 0.5, Q = Q - P[j] + P[i];
        }
    }
    printf("%.1Lf\n", ans);
    return 0;
}