2 条题解
-
0
#include <bits/stdc++.h> #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=100000+10; int n; struct VEC {double x,y;}v[MAXN<<1],s; double ans; int getsq(VEC v) { if(v.x>=0&&v.y>=0) return 1; if(v.x<0&&v.y>=0) return 2; if(v.x<0&&v.y<0) return 3; return 4; } bool operator <(VEC a,VEC b) { if(getsq(a)!=getsq(b)) return getsq(a)<getsq(b); return a.x*b.y-a.y*b.x>0; } VEC operator +(VEC A,VEC B) {return {A.x+B.x,A.y+B.y};} VEC operator -(VEC A,VEC B) {return {A.x-B.x,A.y-B.y};} int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; ffor(i,1,n) cin>>v[i].x>>v[i].y; VEC vc={0,0}; ffor(i,1,n) vc=vc+v[i]; sort(v+1,v+n+1); ffor(i,1,n) v[i+n]=v[i]; int l=1,r=1; s=v[1],ans=max(ans,s.x*s.x+s.y*s.y); while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) { r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y); } ffor(i,2,n) { l++,s=s-v[l-1]; if(r<l) s=v[l],r=l; ans=max(ans,s.x*s.x+s.y*s.y); while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) { r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y); } } cout<<fixed<<setprecision(3)<<ans; return 0; } -
0
#include<bits/stdc++.h> #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=100000+10; int n; struct VEC {double x,y;}v[MAXN<<1],s; double ans; int getsq(VEC v) { if(v.x>=0&&v.y>=0) return 1; if(v.x<0&&v.y>=0) return 2; if(v.x<0&&v.y<0) return 3; return 4; } bool operator <(VEC a,VEC b) { if(getsq(a)!=getsq(b)) return getsq(a)<getsq(b); return a.x*b.y-a.y*b.x>0; } VEC operator +(VEC A,VEC B) {return {A.x+B.x,A.y+B.y};} VEC operator -(VEC A,VEC B) {return {A.x-B.x,A.y-B.y};} int main() { ios::sync_with_stdio(False),cin.tie(0),cout.tie(0); cin>>n; ffor(i,1,n) cin>>v[i].x>>v[i].y; VEC vc={0,0}; ffor(i,1,n) vc=vc+v[i]; sort(v+1,v+n+1); ffor(i,1,n) v[i+n]=v[i]; int l=1,r=1; s=v[1],ans=max(ans,s.x*s.x+s.y*s.y); while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) { r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y); } ffor(i,2,n) { l++,s=s-v[l-1]; if(r<l) s=v[l],r=l; ans=max(ans,s.x*s.x+s.y*s.y); while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) { r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y); } } cout<<fixed<<setprecision(3)<<ans; return 0; }
- 1
信息
- ID
- 2931
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 132
- 已通过
- 0
- 上传者