题目链接点这里
联想到我们算多边形面积时，用源点到边的叉积计算， 我们可以先枚举一个点u，然后以这个点极角排序枚举其他点v,就可以枚举点，这样可以方便计算在计算uv左边的点，从而求出他为边的凸包个数。。。
#include<iostream> #include<cstdio> #include<math.h> #include<algorithm> #include<map> #include<set> #include<bitset> #include<stack> #include<queue> #include<string.h> #include<cstring> #include<vector> #include<time.h> #include<stdlib.h> using namespace std; #define INF 0x3f3f3f3f #define INFLL 0x3f3f3f3f3f3f3f3f #define FIN freopen("input.txt","r",stdin); #define sf(x,y) scanf("x",y) #define pf(x,y) printf("x",y) #define mem(x,y) memset(x,y,sizeof(x)) typedef unsigned long long ULL; typedef long long LL; #define fuck(x) cout<<"["<<x<<"]"<<endl; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef pair<pair<LL,LL>,LL> PIII; typedef pair<LL,LL> PII; const int MX=1e3+10; const LL mod=998244353; const double eps=1e-9; int n; struct Point { LL x, y; double ang; Point() {} Point(LL x,LL y):x(x),y(y) {} bool operator <(const Point &a)const { return ang<a.ang; } } P[MX],R[2*MX]; typedef Point Vector; Vector operator-(Vector A,Vector B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator+(Vector A,Vector B) { return Vector(A.x + B.x, A.y + B.y); } LL Dot(Vector A,Vector B) //点积 { return A.x*B.x+A.y*B.y;//如果改成整形记得加LL } int dcmp(double x) //返回x的正负 { if(fabs(x)<eps)return 0; return x<0?-1:1; } LL Cross(Vector A,Vector B) //叉积 { return A.x*B.y-A.y*B.x;//如果改成整形记得加LL } Point pc; inline int get_seg(Point a) //象限 { if(a.x > 0 && a.y >= 0) return 1; if(a.x <= 0 && a.y > 0) return 2; if(a.x < 0 && a.y <= 0) return 3; return 4; } /*pc为当前排序的中心，通常选最左下角的点（先y后x）*/ //与pc共点的排序后在最前面,极角相同时随机排序 bool cmp(const Point &a, const Point &b) { if(a.x-pc.x==0 && a.y-pc.y==0) return 1; if(b.x-pc.x==0&& b.y-pc.y==0) return 0; int u = get_seg(a - pc), v = get_seg(b - pc); if(u == v) return Cross(a - pc,b - pc) > 0; return u < v; } const double PI=acos(-1); LL er[MX]; LL ans=0; LL solve(int w) { //fuck(w); pc=P[w]; for(int i=0; i<n; i++) { R[i]=P[i]; R[i].ang=atan2(R[i].y-pc.y,R[i].x-pc.x); //cout<<R[i].x<<" "<<R[i].y<<" "<<R[i].ang<<endl; } swap(R[0],R[w]); //cout<<"["<<pc.x<<"]"<<" "<<"["<<pc.y<<"]"<<endl; //sort(R,R+n,cmp); sort(R+1,R+n); for(int i=1; i<n; i++) { R[i+n-1]=R[i]; R[i+n-1].ang+=2*PI; } LL tmp=0; for(int i=1,j=1; i<n; i++) { while(R[j].ang<R[i].ang+PI)j++; tmp=(tmp+((er[j-i-1]-1)*(Cross(pc,R[i])%mod+mod))%mod)%mod; } return tmp; } int main() { er[0]=1; for(int i=1; i<MX; i++)er[i]=er[i-1]*2%mod; int T; cin>>T; while(T--) { ans=0; scanf("%d",&n); for(int i=0; i<n; i++)scanf("%lld%lld",&P[i].x,&P[i].y); for(int i=0; i<n; i++)ans=(ans+solve(i))%mod; cout<<ans<<endl; } return 0; }