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杀我,我浮点数+计算几何 就是过不了,然后换成纯整数处理过了,自闭
代码
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 |
|
总结
1是想到反向计算,我一直在想算三角形然后带其它点,再容斥,就没想出来
2是浮点数精度,哎自闭,还是整数香