題目鏈接

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 (计算几何)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。