计算几何（简单旋转卡壳）2024昆明邀请赛

题目链接

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int>PII;
typedef priority_queue<int> upq;
typedef priority_queue<int,vector<int>,greater<int>> dpq;
const int M=998244353;struct Point{ll x,y;
};
ll cross(Point a,Point b,Point c){ //叉积return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
ll dis(Point a,Point b){ //距离return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);  
}
void solved()
{ll n; cin>>n;ll x,y,r; cin>>x>>y>>r;vector<Point>v(n+1);v[n].x=x; v[n].y=y;for(int i=0;i<n;i++){cin>>v[i].x>>v[i].y;}ll ans=0,now=0;for(int i=0,j=1;i<n;i++){while(1){int next_j=(j+1)%n; ll _cross=cross(v[i],v[next_j],v[n]);		//此处特别注意线段优先级 if(_cross<=0) break;		//维护圆心在分割点左侧，叉积大于0if((__int128)_cross*_cross<(__int128)r*r*dis(v[i],v[next_j])) break; // 判断直线i-net_j到o的距离是否 >= r（通过叉积平方与r2*向量长度平方比较） (可以推得）_cross=cross(v[i],v[j],v[next_j]);now+=abs(_cross);j=next_j;}ans=max(ans,now);int next_i=(i+1)%n;		//移动i指针算减少贡献 ll _cross=cross(v[i],v[j],v[next_i]);now-=abs(_cross);}cout<<ans<<'\n';
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t; cin>>t;while(t--)solved();
}