注:有些输出调试
by 闹闹、 @ 2019-03-12 20:54:39
真正的代码
```
#include<bits/stdc++.h>
using namespace std;
#define db double
#define MAXN 666
#define xl dian
#define esp (1e-9)
const db pi = acos(-1);
struct dian
{
db x,y;
}a[MAXN];
int n,m;
db s;
void rd()
{
srand(20050321);
cin >> n >> s;
for(int i = 1; i <= n; i ++) {
cin >> a[i].x >> a[i].y;
a[i].x += esp*00000.1*(rand()%10-5);
a[i].y += esp*00000.1*(rand()%10-5);
//cout<<a[i].x<<" "<<a[i].y<<"QAQ\n";
}
a[n+1] = a[1];
}
xl operator +(xl a,xl b) {return (xl){a.x+b.x,a.y + b.y};}
xl operator -(xl a,xl b) {return (xl){a.x-b.x,a.y - b.y};}
inline db chaji(xl a,xl b) {
return a.x * b.y - a.y * b.x;
}
inline db dianji(xl a,xl b) {
return a.x * b.x + a.y * b.y;
}
inline db chang(xl a) {
return dianji(a,a);
}
int dcmp(db x)
{
//cout<<x<<"QAQ?\n";
if(x > esp) return 1;
if(x < -esp) return -1;
return 0;
}
inline db juli(dian a,dian b) {
return chang(b-a);
}
xl zhuan(xl a,db r) {
xl x;
x.x = a.x*cos(r) - a.y*sin(r);
x.y = a.x*sin(r) + a.y*cos(r);
return x;
}
db jijiao(xl a) {
return atan2(a.y,a.x);
}
db r;
struct QAQ
{
db p,r;
int q;
}p[MAXN];
int nn;
void jd(dian a,dian b) {
db pp = -jijiao(a-b);
//cout<<a.x<<" "<<a.y<<","<<b.x<<" "<<b.y<<"???\n";
// cout<<pp/pi*180<<"\n";
a = zhuan(a,pp);
b = zhuan(b,pp);
// cout<<a.x<<" "<<a.y<<","<<b.x<<" "<<b.y<<"!\n";
if(dcmp(fabs(a.y) - r) < 0) {
//cout<<a.y - r<<"\n";
db sq = sqrt(r*r - a.y * a.y);
// cout<<sq<<" "<<min(a.x,b.x)<<" "<<max(a.x,b.x)<<"\n";
if(dcmp( - sq - min(a.x,b.x) ) >= 0)
{
nn ++;
p[nn].p = pi/2 + acos(a.y/r) - pp;
if(p[nn].p > pi) p[nn].p -= pi*2;
if(p[nn].p < -pi) p[nn].p += pi*2;
// cout<<p[nn].p/pi*180<<"QAQ\n";
p[nn].q = 0;
}
if(dcmp(sq - max(a.x,b.x) ) <= 0)
{
nn ++;
p[nn].p = pi/2 - acos(a.y/r) - pp;
if(p[nn].p > pi) p[nn].p -= pi*2;
if(p[nn].p < -pi) p[nn].p += pi*2;
// cout<<p[nn].p/pi*180<<"QAQ\n";
p[nn].q = 0;
}
}
}
db mianji(dian a,dian b,dian c)
{
return chaji(b-a,c-a)/2;
}
bool cmp(QAQ a,QAQ b)
{
return dcmp(a.p - b.p) <= 0;
}
bool judge(db x)
{
nn = 0;
r = x;
for(int i = 1; i <= n; i ++) {
nn ++;
p[nn].p = jijiao(a[i]);
if(dcmp(sqrt(chang(a[i])) - r) < 0)
{
p[nn].q = -1;
p[nn].r = sqrt(chang(a[i]));
}
else p[nn].q = 1;
}
for(int i = 1; i <= n; i ++)
jd(a[i],a[i+1]);
sort(p+1,p+nn+1,cmp);
nn ++;
p[nn] = p[1];
db ans = 0;
//for(int i = 1; i <= nn; i ++)
// cout<<p[i].p/pi*180<<" "<<p[i].q<<"!!!!!!\n";
for(int i = 1; i < nn; i ++) {
db jj = fabs(p[i+1].p - p[i].p);
if(jj > pi) jj = pi*2 - jj;
if((p[i].q == 1 || p[i+1].q == 1))
{
// cout<<"!\n";
ans += r*r * (jj)/2;
} else {
if(p[i].q == -1 && p[i+1].q == -1)
{
ans += p[i].r * p[i+1].r*sin(jj)/2;
}else
if(p[i].q == 0 && p[i+1].q == -1)
{
ans += r * p[i+1].r*sin(jj)/2;
}else if(p[i].q == -1 && p[i+1].q == 0)
{
ans += p[i].r * r*sin(jj)/2;
}else ans += r*r*sin(jj)/2;
// cout<<"?\n";
}
// cout<<ans<<"\n";
// cout<<jj/pi*180<<"QAQ\n";
}
// cout<<ans<<" "<<s<<" "<<dcmp(ans-s)<<"\n";
return dcmp(ans-s) >= 0;
}
int main()
{
rd();
db l = esp,r = 10000000000;
while(l + 0.0000001 < r)
{
db mid = (l+r)/2;
if(judge(mid))
{
r = mid;
} else l =mid;
}
printf("%.2lf",l);
return 0;
}
/*
4 4.175
1 1
3 -3
-1 -1
-1 1
4 9
2 2
-2 2
-1 -1
1 -1
4 7.701
0 -2
-2 0
-1 3
1 1
5 29.4
-2 -2
-2 2
1 4
3 2
2 -5
6 0.34
-1.2 -1.0
-3.45 0.8
1.34 5.3
5.31 2.11
5.31 -1.0
4.74 -2.0
6 13.42
4.74 -2.0
5.31 -1.0
5.31 2.11
1.34 5.3
-3.45 0.8
-1.2 -1.0
6 27.77
4.74 -2.0
5.31 -1.0
5.31 2.11
1.34 5.3
-3.45 0.8
-1.2 -1.0
6 39.12
4.74 -2.0
5.31 -1.0
5.31 2.11
1.34 5.3
-3.45 0.8
-1.2 -1.0/
4 320.00
10 10
10 -10
-10 -10
-10 10
4 356.2
10 10
10 -10
-10 -10
-10 10
4 390.00
10 10
10 -10
-10 -10
-10 10
0
3 1.5
1 1
1 -1
-1 -1
*/
```
by 闹闹、 @ 2019-03-12 20:55:53
去你母亲的萌新
by L1ttel_Y @ 2019-03-12 20:57:30
女生可海星
by King_of_gamers @ 2019-03-12 20:57:47
注:udebug第二个数据有边经过0,0的·
但是本题没有
(经本人检验)
by 闹闹、 @ 2019-03-12 20:58:04
已经解决。。。
by Ynoi @ 2019-03-13 08:56:02