CF1146H Satanic Panic

时间:2024-01-18 10:13:38

题目传送门

Description

给定二维平面内\(n\)个点\((n\leq 300)\),求能组成五角星(不要求正五角星)的五元组个数。

Solution

一道小清新的寄蒜几盒计算几何题,代码不到50行。

一个五元组能组成五角星当且仅当五个点都在凸包上,即存在五条连续的连边,使得极角序递增。

先将边按极角序排序,然后\(dp\)转移。

对于每一条边\(u->v\),\(dp_{u, v,1}=1\),转移是\(dp_{S, v, i+1}+=dp_{S,u,i}\),因为极角序递增,所以所有状态都可以转移。

最后的\(Ans=\sum_{i=1}^{n}dp_{i,i,5}\)。

时间复杂度\(O(n^3)\)

话说snuke睡过头了40min,然后在59min拿了这题的首杀。

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
using namespace std;
struct Vector{int x,y;Vector(int a=0,int b=0):x(a),y(b){}};
Vector operator - (Vector a, Vector b){return Vector(a.x-b.x, a.y-b.y);}
int Cross(Vector A, Vector B) {return A.x*B.y-A.y*B.x;}
bool operator < (Vector A, Vector B) {return Cross(A, B)<0;} const int N=305;
Vector p[N];
int dp[N][N][6];
vector<pair<Vector, pair<int, int> > > e; inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
} signed main()
{
int n=read();
rep(i, 1, n) p[i].x=read(), p[i].y=read();
rep(i, 1, n) rep(j, 1, n) if (i^j)
e.push_back(make_pair(Vector(p[j]-p[i]), make_pair(i, j)));
sort(e.begin(), e.end());
for (auto now: e)
{
int u=now.second.first, v=now.second.second;
dp[u][v][1]++;
rep(i, 1, 5) rep(s, 1, n)
dp[s][v][i+1]+=dp[s][u][i];
}
int ans=0;
rep(i, 1, n) ans+=dp[i][i][5];
printf("%lld\n", ans);
return 0;
}