50pts求调,悬赏10元
查看原帖
50pts求调,悬赏10元
455474
lailai0916楼主2024/12/25 16:19
#include <bits/stdc++.h>
using namespace std;

const double pi=acos(-1);
const double eps=1e-8;
const int N=55;
int sgn(double x){return (x>eps)-(x<-eps);}
struct Point
{
	double x,y;
	Point(){}
	Point(double _x,double _y):x(_x),y(_y){}
	Point operator+(Point B){return Point(x+B.x,y+B.y);}
	Point operator-(Point B){return Point(x-B.x,y-B.y);}
	Point operator*(double k){return Point(x*k,y*k);}
	Point operator/(double k){return Point(x/k,y/k);}
}a[N];
double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
double Len(Point A){return sqrt(Dot(A,A));}
double Len2(Point A){return Dot(A,A);}
double f1(Point A,Point B){return Cross(A,B)/2;}
double f2(Point A,Point B,double r){return atan2(Cross(A,B),Dot(A,B))*r*r/2;}
double f(Point A,Point B,double r)
{
	double l1=Len(A),l2=Len(B);
	if(sgn(l1-r)<=0&&sgn(l2-r)<=0)return f1(A,B);
	double a=Len2(B-A);
	double b=Dot(A,B-A)*2;
	double c=Len2(A)-r*r;
	double d=b*b-a*c*4;
	if(sgn(d)<=0)return f2(A,B,r);
	Point C=A+(B-A)*(-b-sqrt(d))/(a*2);
	Point D=A+(B-A)*(-b+sqrt(d))/(a*2);
	if(sgn(l1-r)<=0)return f1(A,D)+f2(D,B,r);
	if(sgn(l2-r)<=0)return f2(A,C,r)+f1(C,B);
	return f2(A,C,r)+f1(C,D)+f2(D,B,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	double s;
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	double l=0,r=10000;
	while(r-l>eps)
	{
		double mid=(l+r)/2,sum=0;
		for(int i=1;i<=n;i++)
		{
			sum+=f(a[i],a[i%n+1],mid);
		}
		if(fabs(sum)>=s)r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(2)<<l<<'\n';
	return 0;
}
2024/12/25 16:19
加载中...