【arc082c】ConvexScore

Source and Judge

arc082c

Record

30min

Analysis

请先思考后再展开

n四方:
把每个凸包用最下面的点表示(多个则最左)
然后极角排序后,跑一个dp,记录内部点的数量(暴力预处理三角形内点的数量)

n三方:
考虑贡献的形式,就是去掉凸包S后子集U数量
然后就会发现(反正我是想不到的),S和U的并是独一无二的,那么只要统计有面积的集合数量即可
枚举点,然后去掉重复计数即可

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
//#define pr pair<double,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=210;
struct Nod{int x,y;}p[MAX_N];
int cross(Nod a,Nod b) {return a.x*b.y-a.y*b.x;}
const int MOD=998244353;
bool v[MAX_N][MAX_N];
int bin[MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]*2%MOD;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
int ans=bin[n]-1-n;//printf("ans=%d\n",ans);
for(int a=1;a<=n;a++)
for(int b=a+1;b<=n;b++)
{
int mi,mx;
if(p[a].x==p[b].x) {if(p[a].y<p[b].y) mi=a,mx=b; else mi=b,mx=a;}
else
{
if(p[a].x<p[b].x) mi=a,mx=b;
else mi=b,mx=a;
}
int tot=2;
for(int c=1;c<=n;c++) if(c!=a and c!=b)
{
if(cross(
(Nod){p[a].x-p[b].x,p[a].y-p[b].y},
(Nod){p[a].x-p[c].x,p[a].y-p[c].y})==0)
{
if(p[a].x==p[b].x)
{
if(p[c].y<p[mi].y) mi=c;
else if(p[c].y>p[mx].y) mx=c;
}
else
{
if(p[c].x<p[mi].x) mi=c;
else if(p[c].x>p[mx].x) mx=c;
}
tot++;
}
}
if(v[mi][mx]) continue;
v[mi][mx]=1;
ans-=bin[tot]-tot-1;
ans%=MOD;
//printf("(%d,%d,%d,%d)=%d\n",mi,mx,a,b,tot);
}
printf("%d",(ans+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b53a.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%