Hello 2020

E

原题链接

2500评分

大意

平面上n个点,不存在3个共线,

对于所有(点p,另外四个点),如果另外四个点能包围点p则计数+1,对于同样的p和选中的4个点,不论有几种方式,只要能包围就计数+1

求p依次取遍所有点的计数和

范围

5<=n<=2500,

3s

1024MB

官方题解

https://codeforces.com/blog/entry/72804

题解

计算几何我就开始自闭了

最终要求的为sum{是否包围(p,另外四个点)},反向问题为

sum{是否不包围(p,另外四个点)}

考虑选取总方案为

$n*C_{n-1}^4$

如果选取的4个点,对于点p在同一个半圆内,那么选取的4个点无法包围,如果不在同一个半圆内则能包围

如果选取的4个点在同一个半圆内,则它们以p为顶点,构成的夹角小于180度,则这个夹角上存在顺时针的起始和结束点

假设选取点p和起始点q1,那么剩余三个点q2,q3,q4,与p和q1构成的夹角应该在0 到180度之间(且保证方向,也就是-0到-180度是不可取的)

这样对于每一个不包围的4个点,能做到不重不漏的计算

O(p枚举 * 计算几何排序和遍历)

然后 计算几何和浮点数和test9杀我,我浮点数+计算几何 就是过不了,然后换成纯整数处理过了,自闭

代码

accept

68473398 Wrong answer on test 9

68473313 Wrong answer on test 9

68473215 Runtime error on test 9

68473189 Runtime error on test 9

68473103 Runtime error on test 9

68473021 Runtime error on test 9

68471693 Runtime error on test 9

68471651 Runtime error on test 9

68471600 Wrong answer on test 9

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const long double pi = acos(-1.0);

pair<ll,ll>xy[3010];
pair<ll,ll>xysort[3010];
int n;

template<class T1, class T2>
inline const pair<T1, T2> operator-(const pair<T1, T2>&p1, const pair<T1, T2>&p2) {
return {
p1.first - p2.first,
p1.second - p2.second
};
}

ll cross(pair<ll,ll> vec1,pair<ll,ll> vec2){
auto [x1,y1] = vec1;
auto [x2,y2] = vec2;
return x1*y2-x2*y1;
}

int main() {
ll n;
scanf("%lld",&n);
rep(i,0,n){
ll x,y;
scanf("%lld %lld",&x,&y);
xy[i] = {x,y};
}
ll res = n * ((n-1) * (n-2) * (n-3) * (n-4) / (1*2*3*4));
rep(i,0,n){
rep(j,0,n){
if(i == j)continue;
xysort[j>i?j-1:j] = xy[j];
}
sort(xysort+1,xysort+n-1,
[i](const pair<ll,ll>p0,const pair<ll,ll>p1) -> bool{
ll cross0 = cross(p0-xy[i],xysort[0]-xy[i]);
ll cross1 = cross(p1-xy[i],xysort[0]-xy[i]);
if(cross0 >=0 && cross1 < 0){
return true;
}else if(cross0 < 0 && cross1 >= 0){
return false;
}
ll cross01=cross(p0-xy[i],p1-xy[i]);
return cross01 <= 0;
});
int index = 1;
// 四个点的起始点,首尾游标
rep(j,0,n-1){
while(index < j + n-1){
ll crossij = cross(xysort[index%(n-1)]-xy[i],xysort[j]-xy[i]);
if(crossij >= 0 ){
index++;
}else{
break;
}
}
// C_cnt^3
ll cnt = index - j - 1;
res -= (cnt * (cnt - 1) * (cnt - 2)) / (1*2*3);
}
}
printf("%lld\n",res);
return 0;
}

总结

1是想到反向计算,我一直在想算三角形然后带其它点,再容斥,就没想出来

2是浮点数精度,哎自闭,还是整数香