ARC082C ConvexScore

简要题意

给定n个点,定义一个凸多边形包含点数s为:这个凸多边形覆盖的点数-这个凸多边形的角数(每一个角 )

设总点集为A。 这个凸多边形的分值为为:2s2^s

求由这n个点构成的所有凸多边形的分值和mod998244353mod 998244353

简要题解

2s2^s是这s个点可选可不选的总方案数。 则答案是

S=stS=s\cup t 我们可以直接枚举SS。当SS内的点不构成一条线段或只有一个点的时候,它有唯一的一个凸包,则它对答案的贡献就为1。

首先我们先不考虑线段,则答案为2nn12^n-n-1(每个点选或不选-单点-空集) 接着我们找出每一条线段(点数>1>1),对于每条线段,假如有m个点,则它对答案的减少就为2mm12^m-m-1(每个点选或不选-单点和空集没有之前已经去掉了)

简要代码

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
/*
Author: CNYALI_LK
LANG: C++
PROG: E.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
const ll mod=998244353;
ll p[233];
struct zb{
ll x,y;
};
zb a[233];
ll cmp(zb a,zb b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ll n,ans;
scanf("%lld",&n);
p[0]=1;
for(ll i=1;i<=n;++i){p[i]=p[i-1]<<1;if(p[i]>=mod)p[i]-=mod;scanf("%lld%lld",&a[i].x,&a[i].y);}
sort(a+1,a+n+1,cmp);
ans=p[n]-n-1;
for(ll i=1;i<=n;++i)for(ll j=i+1;j<=n;++j){
ll no=0;
for(ll k=1;k<j;++k)if(k!=i&&(a[j].x-a[i].x)*(a[i].y-a[k].y)==(a[j].y-a[i].y)*(a[i].x-a[k].x)){no=1;break;}
if(!no){
/// debug("(%lld,%lld) (%lld,%lld)",a[i].x,a[i].y,a[j].x,a[j].y);
ll tot=2;
for(ll k=j+1;k<=n;++k){
if((a[j].x-a[i].x)*(a[i].y-a[k].y)==(a[j].y-a[i].y)*(a[i].x-a[k].x)){++tot;/*debug(" (%lld,%lld)",a[k].x,a[k].y);*/}
}
// debug("\n");
ans-=p[tot]-tot-1;
}
}
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}
文章目录
  1. 1. 简要题意
  2. 2. 简要题解
  3. 3. 简要代码
|

博客使用Disqus作为评论系统