每日一水第30弹 省赛C题

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5519

给你1000个点,问对于所有点集构成的凸包的面积之和的两倍。

玛雅, 一开始就把题目看错了,两种点集,一种凸包我算成一种了。

如果你会计算多边形的面积,你就会观察到实际上一个多边形的面积是由n条边跟原点构成的三角形的有向面积相加得到的。

所以问题就归结到每条边作为凸包的某一条边被算到了几次。

然后就是极角排序,枚举每条边,再算左侧有多少个点,左侧的点的任意一种组合形式,这条边的代价都会被算一次。

真是个惊天大水题啊。

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
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-9;
struct Point
{
    double x,y;
    double ang;
    bool operator == (const Point&cmp) const{
        return x == cmp.x && y== cmp.y;
    }
}q[2010],p[1010];
Point center;
int cmp(Point a, Point b)
{
    return a.ang < b.ang;
}
int two[1010];
int main()
{
    srand(time(NULL));
    two[0] = 1;
    for(int i = 1; i <= 1000; i++) two[i] = two[i - 1] * 2 % mod;
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        int ret = 0;
        for(int i = 0; i < n;i++) {
            center = p[i];
            int tot = 0;
            for(int j = 0; j < n; j++) if(j != i){
                q[tot++] = p[j];
                q[tot - 1].ang = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
            }
            sort(q, q + tot, cmp);
            for(int j = tot; j < 2*tot; j++) {
                q[j].ang = q[j - tot].ang + 2 * pi;
            }
            for(int j = 0; j < tot; j++) {
                if(q[j] == center) {
                    continue;
                }
                int l = 0, r = tot - 1;
                int best = 0;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if(q[j + mid].ang - q[j].ang - pi < -eps) {
                        best = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                int mul = ((two[best] - 1) % mod + mod) % mod;
                int x1 = center.x, y1 = center.y;
                int x2 = q[j].x, y2 = q[j].y;
                int tm = ((1LL*x1*y2%mod - 1LL*x2*y1%mod) % mod + mod) % mod;
                ret = (ret + 1LL * tm * mul % mod) % mod;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

 

09fa513d269759ee7a20b9deb2fb43166d22dfb7

 

 

 

 

每日一水第30弹 省赛C题》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注