题目链接
https://codeforces.com/contest/613/problem/A
思路
求多边形绕一定点扫过的圆环面积。
外圆半径r2为多边形顶点到定点的最长距离。内圆半径r1为多边形的边到定点的最短距离。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e5+10;
int inf=1e9;
void read(int &x){
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
struct node{
double x,y;
};
node p[maxn],s[maxn],st;
//求边长
double bian(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(b.y-a.y)*(b.y-a.y);
}
int n;
double PointToSegDist(double x, double y, double x1, double y1, double x2, double y2){
double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);
if (cross <= 0) return (x - x1) * (x - x1) + (y - y1) * (y - y1);
double d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
if (cross >= d2) return (x - x2) * (x - x2) + (y - y2) * (y - y2);
double r = cross / d2;
double px = x1 + (x2 - x1) * r;
double py = y1 + (y2 - y1) * r;
return (x - px) * (x - px) + (py - y) * (py - y);
}
int main(){
int i;
double r1,r2=0,pi=3.1415926535;
read(n);scanf("%lf%lf",&st.x,&st.y);
for(i=0;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
r2=max(r2,bian(p[i],st));
}
r1=r2;
for(i=0;i<n-1;i++)r1=min(r1,PointToSegDist(st.x,st.y,p[i].x,p[i].y,p[i+1].x,p[i+1].y));
r1=min(r1,PointToSegDist(st.x,st.y,p[0].x,p[0].y,p[n-1].x,p[n-1].y));
double ans=pi*(r2-r1);
printf("%.8lf",ans);
return 0;
}
