CF528E Triangles 3000

发表于 | 阅读数

平面上有若干条直线，保证不平行，不会三线共点。求任选三条直线出来围出的三角形的面积的期望。

$S_{ABC}=\frac{1}{2}(OA\times OB+OB\times OC+ OC\times OA)$
（其中有正有负）
对于每个交点我们可以计算他对三角形的贡献。

假设三角形的交点$B\rightarrow A \rightarrow C$顺时针。这样算出来是正的。

对于一条线$AB$上的点$A$,斜率大的线交$C$，斜率小的$D$,产生贡献总是$OD\times OC$（画图可知）。即边扫描一圈，边计算。极角排序之后就能不重不漏了。

  • 通过$ax+bx+c=0$，构造两个点，就可以套直线相交的模版了
  • 这里极角排序使用$atan2$,然后保证$age\in [0,pi]$
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const double pi = acos(-1.0L);
struct point
{
    double x, y;
    double v, li;
    point operator-(const point &p) const { return (point){x - p.x, y - p.y}; };
    point operator+(const point &p) const { return (point){x + p.x, y + p.y}; };
    double operator^(const point &p) const { return x * p.y - y * p.x; };
    double operator*(const point &p) const { return x * p.x + y * p.y; };
    point operator*(const double &p) const { return (point){x * p, y * p}; };
    double dis() const { return sqrt(x * x + y * y); }

} p[N];
struct line
{
    point p1, p2;
    double ag;
} le[N];
bool cmp(line x, line y)
{
    return x.ag < y.ag;
}
vector<point> g;
double eare(point p1, point p2, point p3)
{
    point p4 = p2 - p1;
    point p5 = p3 - p1;
    return p4 ^ p5;
}
// bool cmp(point p1, point p2)
// {
//     p1 = p1 - g[pos];
//     p2 = p2 - g[pos];
//     return ((p1 ^ p2) == 0 ? (p1 * p1) < (p2 * p2) : (p1 ^ p2) > 0);
// }
point inter_point(point a1, point a2, point b1, point b2) ///返回直线AB和线段CD的交点
{
    // if (!intersect(A, B, C, D))
    //     return {-INF * 1.0, 0}; ///判断直线AB是否与线段CD相交，不相交必须须特判
    point a = a2 - a1;
    point b = b2 - b1;
    double t = ((b1 ^ b) - (a1 ^ b)) / (a ^ b);

    return (a1 + a * t);
}

int n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 0)
            le[i] = (line){(point){0, c * 1.0 / (b * 1.0)}, (point){100, c * 1.0 / (b * 1.0)}};
        else if (b == 0)
            le[i] = (line){(point){c * 1.0 / (a * 1.0), 0}, (point){c * 1.0 / (a * 1.0), 100}};
        else
            le[i] = (line){(point){0, c * 1.0 / (b * 1.0)}, (point){100, (a * -100 + c + 0.0) / (b * 1.0)}};
        le[i].ag = atan2((le[i].p2 - le[i].p1).y, (le[i].p2 - le[i].p1).x);
        if (le[i].ag < 0)
            le[i].ag += 2 * pi;
    }
    sort(le, le + n, cmp);
    double ans = 0;
    for (int i = 0; i < n; i++)
    {
        //cout << le[i].ag / 3.14 * 180 << endl;
        point sum = (point){0, 0};
        for (int j = i + 1; j < n + i; j++)
        {
            point inst = inter_point(le[i].p1, le[i].p2, le[j % n].p1, le[j % n].p2);
            ans += (sum ^ inst), sum = sum + inst;
        }
    }
    ans /= 1.0 * n * (n - 1) * (n - 2) / 3;
    printf("%.9lf", ans);
}