QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363251 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team135# | WA | 1ms | 4068kb | C++20 | 4.0kb | 2024-03-23 19:58:16 | 2024-03-23 19:58:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
#define y1 rtgerf
#define tm hytgrfgef
#define pt pair<int,int>
#define x first
#define y second
#define Point pt
double dist (Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int sign(int x) {
if (x == 0)
return 0;
else if (x < 0)
return -1;
else
return 1;
}
bool cmp (Point a, Point b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
int sq (Point a, Point b, Point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool cw (Point a, Point b, Point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
bool ccw (Point a, Point b, Point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
void convex_hull (vector<Point> & a) {
if (a.size() == 1) return;
sort (a.begin(), a.end(), &cmp);
Point p1 = a[0], p2 = a.back();
vector<Point> up, down;
up.push_back (p1);
down.push_back (p1);
for (size_t i=1; i<a.size(); ++i) {
if (i==a.size()-1 || cw (p1, a[i], p2)) {
while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
up.pop_back();
up.push_back (a[i]);
}
if (i==a.size()-1 || ccw (p1, a[i], p2)) {
while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
down.pop_back();
down.push_back (a[i]);
}
}
a.clear();
for (size_t i=0; i<up.size(); ++i)
a.push_back (up[i]);
for (size_t i=down.size()-2; i>0; --i)
a.push_back (down[i]);
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,r;cin>>n>>r;if(n==1) {cout<<0;return 0;}
vector<pt> a(n);for(int i=0;i<n;++i) {cin>>a[i].x>>a[i].y;} convex_hull(a); n=a.size(); if(n==1) {cout<<0;return 0;}
int vals[2*n]={0};for(int i=0;i<2*n;++i) {vals[i]=(a[i%n].x*a[(i+1)%n].y-a[i%n].y*a[(i+1)%n].x);}
int pr[2*n+1]={0};for(int i=0;i<2*n;++i) {pr[i+1]=pr[i]+vals[i];}
double res=0;
for(auto h:a) debug(h.x,h.y);
auto f1=[&](int i,int j)->double
{
if(j<i) {j+=n;}
int have=pr[j]-pr[i];
int add=(a[j%n].x*a[i%n].y-a[j%n].y*a[i%n].x);
double ans=abs(have+add)/2.0;
debug(i,j,have,add,ans);
return ans;
};
auto f2=[&](pt u,pt v,pt w)->double
{
double answ=0;
double len=dist(u,v);
pt o=pt(0,0);
double h=(abs(sq(u,v,o)))/len;
if(sq(u,v,w)*sq(u,v,o)>=0)
{
answ=max(answ,len*(r-h)/2.0);
}
if(sq(u,v,w)*sq(u,v,o)<=0)
{
answ=max(answ,len*(r+h)/2.0);
}
return answ;
};
auto f=[&](int i,int j)
{
if(i==j) return;
debug(i,j);
res=max(res,f1(i,j)+f2(a[i],a[j],a[(i+1)%n]));
res=max(res,f1(j,i)+f2(a[i],a[j],a[(j+1)%n]));
};
for(int i=0;i<n;++i)
{
int low=1;int up=n;
while(up-low>2)
{
int l1=(2*low+up)/3;int r1=(low+2*up)/3;
int vall=abs(sq(a[i],a[(i+1)%n],a[(i+l1)%n]));int valr=abs(sq(a[i],a[(i+1)%n],a[(i+r1)%n]));
if(vall<valr) {up=r1;} else {low=l1;}
}
int cur=low;
for(int j=low+1;j<up;++j)
{
if(abs(sq(a[i],a[(i+1)%n],a[(i+j)%n]))<abs(sq(a[i],a[(i+1)%n],a[(i+cur)%n])))
{
cur=j;
}
}
for(int i1:{i%n,(i+1)%n,(i+n-1)%n})
{
for(int j1:{cur%n,(cur+1)%n,(cur+n-1)%n})
{
f(i1,j1);
}
}
}
cout<<setprecision(25)<<res;
return 0;
}
/*
3 5
5 0
-5 0
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4040kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
2 100 17 7 19 90
output:
4849.704644437563729297835
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 100 13 37
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.424949238076806068
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.5625617660116404295
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.595499957911670208
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.4944640259491279721
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 4012kb
input:
1000 10000 -9998 -136 -9996 -245 -9995 -280 -9993 -347 -9991 -397 -9989 -440 -9985 -525 -9984 -545 -9983 -564 -9981 -599 -9979 -632 -9973 -721 -9971 -747 -9966 -810 -9963 -846 -9957 -916 -9953 -958 -9948 -1008 -9945 -1037 -9938 -1103 -9927 -1196 -9920 -1253 -9913 -1308 -9908 -1346 -9891 -1465 -9874 ...
output:
314026171.5
result:
wrong answer 1st numbers differ - expected: '314026591.7801104', found: '314026171.5000000', error = '0.0000013'