Codeforces 1284E New Year and Castle Building (计算几何)

题目链接

https://codeforces.com/contest/1284/problem/E

题解

我们计算选出 \(3\) 个点构成三角形覆盖的点数之和，这个值乘以 \(\frac{(n-4)}{2}\) 就是答案。这是因为对于任意一个（凸或凹，根据题意凹的多种凹法只算一次）四边形，从 \(4\) 个顶点中选出 \(3\) 个构成三角形的 \(4\) 种方案中每个被四边形覆盖的点恰好被 \(2\) 种方案覆盖。
然后就比较套路了，补集转化，枚举一个点求有多少个三角形不包含它，然后其余的点以它为中心按极角排序，枚举最顺时针的那个，算从它的一侧选出两个点的方案数。
不过似乎没发现三角形那个性质大力扫描线也能做，好题->垃圾题？
时间复杂度 \(O(n^2\log n)\).

代码

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 2500; struct Point {llong x,y;Point() {}Point(llong _x,llong _y):x(_x),y(_y) {}int quadrant() {return x>0?(y<0):(y<=0);} } a[mxN+3],b[(mxN<<1)+3]; typedef Point Vector; Point operator +(Point x,Point y) {return Point(x.x+y.x,x.y+y.y);} Point operator -(Point x,Point y) {return Point(x.x-y.x,x.y-y.y);} llong Cross(Vector x,Vector y) {return x.x*y.y-x.y*y.x;}int n;bool cmp_ang(Point x,Point y) {return x.quadrant()^y.quadrant()?x.quadrant()<y.quadrant():Cross(x,y)>0;}int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%I64d%I64d",&a[i].x,&a[i].y);llong ans = 0ll;for(int i=1; i<=n; i++){for(int j=1; j<=n; j++) b[j] = a[j]-a[i]; swap(b[i],b[1]);sort(b+2,b+n+1,cmp_ang); // printf("i=%d\n",i); // for(int j=2; j<=n; j++) printf("(%lld,%lld)\n",b[j].x,b[j].y);for(int j=2; j<=n; j++) b[n-1+j] = b[j];int j,k; llong cur = 0ll;for(j=2,k=3; j<=n; j++){while(k<=j||Cross(b[j],b[k])>0) {k++;}int cnt = j+n-1-k; // printf("j=%d k=%d cnt=%d\n",j,k,cnt);cur += 1ll*cnt*(cnt-1ll)/2ll;}ans += cur;}ans = (1ll*n*(n-1ll)*(n-2ll)*(n-3ll)/6ll-ans)*(n-4ll)/2ll;printf("%I64d\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的Codeforces 1284E New Year and Castle Building (计算几何)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。