QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461639 | #784. 旋转卡壳 | Purslane | 0 | 1ms | 4148kb | C++14 | 2.3kb | 2024-07-02 21:06:47 | 2024-07-02 21:06:47 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define double long double
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
namespace CALCULATING_GEOMETRY {
struct Point {double x,y;};
Point operator +(Point A,Point B) {return {A.x+B.x,A.y+B.y};}
Point operator -(Point A,Point B) {return {A.x-B.x,A.y-B.y};}
Point operator *(Point A,double lam) {return {A.x*lam,A.y*lam};}
double operator *(Point A,Point B) {return A.x*B.y-A.y*B.x;}
double operator ^(Point A,Point B) {return A.x*B.x+A.y*B.y;}
bool operator <(Point A,Point B) {if(A.x!=B.x) return A.x<B.x;return A.y<B.y;}
int tot;Point t[MAXN];
vector<Point> convex_hull(vector<Point> vc) {
int n=vc.size();
sort(vc.begin(),vc.end());
tot=0; int lst=1;
ffor(i,0,n-1) {
if(tot<=lst) t[++tot]=vc[i];
else {
while(tot>lst&&(t[tot]-t[tot-1])*(vc[i]-t[tot])<=1e-10) tot--;
t[++tot]=vc[i];
}
}
lst=tot;
roff(i,n-2,0) {
if(tot<=lst) t[++tot]=vc[i];
else {
while(tot>lst&&(t[tot]-t[tot-1])*(vc[i]-t[tot])<=1e-10) tot--;
t[++tot]=vc[i];
}
}
vector<Point> res;
ffor(i,1,tot-1) res.push_back(t[i]);
return res;
}
struct Line {Point p,d;};
}using namespace CALCULATING_GEOMETRY;
int n; vector<Point> vc;
double p_p_dis(Point A,Point B) {auto calc=A-B;return sqrt(calc.x*calc.x+calc.y*calc.y);}
double p_l_dis(Point o,Point p1,Point p2) {return abs((o-p1)*(p2-p1))/p_p_dis(p1,p2);}
int nxt(int u,int n) {return (u+1)%n;}
Point cross(Line A,Line B) {
double k=((B.p-A.p)*B.d)/(A.d*B.d);
return A.p+(A.d*k);
}
#define nxt ((p+1)%vc.size())
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
ffor(i,1,n) {
int x,y;
cin>>x>>y,vc.push_back({x,y});
}
vc=convex_hull(vc);
if(vc.size()==2) return cout<<p_p_dis(vc[0],vc[1]),0;
int p=0;
while(p_l_dis(vc[nxt],vc[0],vc[vc.size()-1])>=p_l_dis(vc[p],vc[0],vc[vc.size()-1])) p=nxt;
double ans=max(p_p_dis(vc[0],vc[p]),p_p_dis(vc[vc.size()-1],vc[p]));
ffor(i,0,vc.size()-2) {
if(p_l_dis(vc[nxt],vc[i],vc[i+1])>=p_l_dis(vc[p],vc[i],vc[i+1])) p=nxt;
ans=max(ans,max(p_p_dis(vc[i],vc[p]),p_p_dis(vc[i+1],vc[p])));
}
cout<<fixed<<setprecision(10)<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 1ms
memory: 3996kb
input:
1000 0 0 -997615 -8573 -1988394 -28911 -2726572 -44296 -3491635 -60392 -4419752 -82814 -5298550 -105946 -5723430 -118453 -6608257 -147267 -7034966 -161982 -7563964 -181682 -8507871 -222865 -9499799 -271846 -10090186 -303547 -10400262 -322989 -10614073 -339725 -11081438 -378596 -11791568 -439127 -127...
output:
274339223.1895613901
result:
ok found '274339223.1895614', expected '274339223.1895614', error '0.0000000'
Test #2:
score: -10
Wrong Answer
time: 1ms
memory: 4148kb
input:
1000 0 0 -887614 -1937 -1459359 -3808 -2421409 -24096 -3273181 -48456 -3917594 -76664 -4402753 -100164 -5375022 -150897 -5993935 -192089 -6587159 -238825 -7549680 -333298 -8330993 -416479 -9244392 -515027 -10010900 -598589 -10374584 -640275 -10767641 -686907 -11173081 -741316 -11821952 -833327 -1260...
output:
262370087.0661462524
result:
wrong answer 1st numbers differ - expected: '262687047.9274906', found: '262370087.0661463', error = '0.0012066'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%