QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#363240 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team135# | WA | 0ms | 4016kb | C++20 | 3.8kb | 2024-03-23 19:52:03 | 2024-03-23 19:52:03 |
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;
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;
}
}
f(i,cur);f(cur,i);
}
cout<<setprecision(25)<<res;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4016kb
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: 3844kb
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: 3888kb
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: 3844kb
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: 3800kb
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: -100
Wrong Answer
time: 0ms
memory: 3908kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
540000
result:
wrong answer 1st numbers differ - expected: '732310.5625618', found: '540000.0000000', error = '0.2626079'