2 条题解

  • 0
    @ 2025-10-8 17:03:36
    #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
      @ 2025-10-8 17:03:21
      #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

      【计算几何 随机化】BZOJ1278 向量 vector

      信息

      ID
      2931
      时间
      1000ms
      内存
      512MiB
      难度
      10
      标签
      递交数
      132
      已通过
      0
      上传者