2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const double eps=1e-8; const int N=5e4+10; struct Point { double x,y; Point(){} Point(double a,double b):x(a),y(b){} void input(){scanf("%lf%lf",&x,&y);} friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;} friend bool cmpy(Point a, Point b){return a.y!=b.y?a.y<b.y:a.x<b.x;} friend Point operator+(Point a,Point b){ return {a.x+b.x,a.y+b.y};} friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};} friend Point operator*(Point a, double p){return {a.x*p, a.y*p};} friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;} friend double dot(Point a,Point b){return a.x*b.x+a.y*b.y;} friend double dis(Point a,Point b){Point p=a-b;return sqrt(p.x*p.x+p.y*p.y);} friend Point rotate(Point a,Point b){ return {a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x}; } }P[N],sta[N];int n,top; void Andrew() { sort(P+1,P+n+1); top=0; for(int i=1;i<=n;i++) { while( top>1 && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--; sta[++top]=P[i]; } int t=top; for(int i=n-1;i>=1;i--) { while( top>t && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--; sta[++top]=P[i]; } n=top-1; } void rotating_calipers()//旋转卡壳 { double ans=1e20; int a,b,c; a=b=2; //上a,右b,左c for(int i=1; i<=n; i++) { while(det(sta[i+1]-sta[i],sta[a]-sta[i])<det(sta[i+1]-sta[i],sta[a+1]-sta[i]))a=a%n+1; while(dot(sta[i+1]-sta[i],sta[ b ]-sta[i])<dot(sta[i+1]-sta[i],sta[b+1]-sta[i]))b=b%n+1; if(i==1)c=a; while(dot(sta[i]-sta[i+1],sta[c]-sta[i+1])<dot(sta[i]-sta[i+1],sta[c+1]-sta[i+1]))c=c%n+1; double d=dis(sta[i],sta[i+1]); double H=det(sta[i+1]-sta[i],sta[a]-sta[i])/d; double R=dot(sta[i+1]-sta[i],sta[ b ]-sta[i])/d; double L=dot(sta[i]-sta[i+1],sta[c]-sta[i+1])/d; if(ans>(R+L-d)*H) { ans=(R+L-d)*H; P[1]=sta[i+1]+(sta[i]-sta[i+1])*(L/d); P[2]=sta[i]+(sta[i+1]-sta[i])*(R/d); P[3]=P[2]+rotate(sta[i+1]-sta[i],Point{0,1})*(H/d); P[4]=P[1]+rotate(sta[i+1]-sta[i],Point{0,1})*(H/d); } } printf("%.5lf\n",ans); for(int i=1; i<=4; i++) { if(fabs(P[i].x)<=eps) P[i].x=0;//避免-0.00000 if(fabs(P[i].y)<=eps) P[i].y=0; } int k=1; for(int i=2; i<=4; i++) if(cmpy(P[i],P[k]))k=i; //找最低点 for(int i=1; i<=4; i++) { printf("%.5lf %.5lf\n",P[k].x,P[k].y); k=k%4+1; } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++)P[i].input(); Andrew(); rotating_calipers(); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:03:05
#include<bits/stdc++.h> using namespace std; const double eps=1e-8; const int N=5e4+10; struct Point { double x,y; Point(){} Point(double a,double b):x(a),y(b){} void input(){scanf("%lf%lf",&x,&y);} friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;} friend bool cmpy(Point a, Point b){return a.y!=b.y?a.y<b.y:a.x<b.x;} friend Point operator+(Point a,Point b){ return {a.x+b.x,a.y+b.y};} friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};} friend Point operator*(Point a, double p){return {a.x*p, a.y*p};} friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;} friend double dot(Point a,Point b){return a.x*b.x+a.y*b.y;} friend double dis(Point a,Point b){Point p=a-b;return sqrt(p.x*p.x+p.y*p.y);} friend Point rotate(Point a,Point b){ return {a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x}; } }P[N],sta[N];int n,top; void Andrew() { sort(P+1,P+n+1); top=0; for(int i=1;i<=n;i++) { while( top>1 && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--; sta[++top]=P[i]; } int t=top; for(int i=n-1;i>=1;i--) { while( top>t && det(sta[top]-sta[top-1],P[i]-sta[top-1])<=0 ) top--; sta[++top]=P[i]; } n=top-1; } void rotating_calipers()//旋转卡壳 { double ans=1e20; int a,b,c; a=b=2; //上a,右b,左c for(int i=1; i<=n; i++) { while(det(sta[i+1]-sta[i],sta[a]-sta[i])<det(sta[i+1]-sta[i],sta[a+1]-sta[i]))a=a%n+1; while(dot(sta[i+1]-sta[i],sta[ b ]-sta[i])<dot(sta[i+1]-sta[i],sta[b+1]-sta[i]))b=b%n+1; if(i==1)c=a; while(dot(sta[i]-sta[i+1],sta[c]-sta[i+1])<dot(sta[i]-sta[i+1],sta[c+1]-sta[i+1]))c=c%n+1; double d=dis(sta[i],sta[i+1]); double H=det(sta[i+1]-sta[i],sta[a]-sta[i])/d; double R=dot(sta[i+1]-sta[i],sta[ b ]-sta[i])/d; double L=dot(sta[i]-sta[i+1],sta[c]-sta[i+1])/d; if(ans>(R+L-d)*H) { ans=(R+L-d)*H; P[1]=sta[i+1]+(sta[i]-sta[i+1])*(L/d); P[2]=sta[i]+(sta[i+1]-sta[i])*(R/d); P[3]=P[2]+rotate(sta[i+1]-sta[i],Point{0,1})*(H/d); P[4]=P[1]+rotate(sta[i+1]-sta[i],Point{0,1})*(H/d); } } printf("%.5lf\n",ans); for(int i=1; i<=4; i++) { if(fabs(P[i].x)<=eps) P[i].x=0;//避免-0.00000 if(fabs(P[i].y)<=eps) P[i].y=0; } int k=1; for(int i=2; i<=4; i++) if(cmpy(P[i],P[k]))k=i; //找最低点 for(int i=1; i<=4; i++) { printf("%.5lf %.5lf\n",P[k].x,P[k].y); k=k%4+1; } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++)P[i].input(); Andrew(); rotating_calipers(); return 0; }
- 1
