题面: 洛谷 https://www.luogu.org/problemnew/show/P3187
解析
板题, 旋转卡壳即可.
代码
- // luogu-judger-enable-o2
- #include<bits/stdc++.h>
- #define N 50005
- using namespace std;
- #define gc() getchar()
- inline int In(){
- char c=gc(); int x=0,ft=1;
- for(;c<'0'||c>'9';c=gc()) if(c=='-') ft=-1;
- for(;c>='0'&&c<='9';c=gc()) x=x*10+c-'0';
- return x*ft;
- }
- const double eps=1e-6,Pi=acos(-1.0);
- inline int dcmp(double x){
- if(fabs(x)<eps) return 0;
- else return x<0?-1:1;
- }
- struct Point{
- double x,y;
- Point(double x=0,double y=0):x(x),y(y) {}
- bool operator <(const Point& p) const { return dcmp(x-p.x)==0?y<p.y:x<p.x; }
- }p[N],poi[N],q[5];
- typedef Point Vector;
- Vector operator + (Vector a,Vector b){ return Vector(a.x+b.x,a.y+b.y); }
- Vector operator - (Vector a,Vector b){ return Vector(a.x-b.x,a.y-b.y); }
- Vector operator * (Vector a,double p){ return Vector(a.x*p,a.y*p); }
- Vector operator / (Vector a,double p){ return Vector(a.x/p,a.y/p); }
- inline double Cross(Vector a,Vector b){
- return a.x*b.y-a.y*b.x;
- }
- inline double Dot(Vector a,Vector b){
- return a.x*b.x+a.y*b.y;
- }
- inline double Len(Vector a){
- return sqrt(Dot(a,a));
- }
- inline double Dis(Point a,Point u,Point v){
- return fabs(Cross(a-u,v-u))/Len(v-u);
- }
- inline Point Get_Poi(Point P,Point A,Point B){
- Vector v=B-A;
- return A+v*(Dot(v,P-A)/Dot(v,v));
- }
- inline Vector Rotate(Vector a,double rad){
- return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
- }
- inline int ConvexHull(Point* p,int n,Point* ch){
- sort(p+1,p+1+n); int top=0;
- for(int i=1;i<=n;++i){
- while(top>1&&dcmp(Cross(ch[top]-ch[top-1],p[i]-ch[top-1]))<=0) --top;
- ch[++top]=p[i];
- }
- int k=top;
- for(int i=n-1;i;--i){
- while(top>k&&dcmp(Cross(ch[top]-ch[top-1],p[i]-ch[top-1]))<=0) --top;
- ch[++top]=p[i];
- }
- if(n>1) --top; return top;
- }
- inline void print(){
- for(int i=1;i<=4;++i) q[i].x=(int)(q[i].x+0.5),q[i].y=(int)(q[i].y+0.5);
- int w,x,y,z,flag=0; w=x=y=z=1;
- for(int i=2;i<=4;++i){
- if(q[i].y<q[w].y) w=i;
- if(q[i].y>q[x].y) x=i;
- if(q[i].x<q[y].x) y=i;
- if(q[i].x>q[z].x) z=i;
- }
- for(int i=1;i<=4;++i) if(i!=w&&dcmp(q[i].y-q[w].y)==0) flag=1;
- if(!flag){
- printf("%.5lf %.5lf\n",q[w].x,q[w].y);
- printf("%.5lf %.5lf\n",q[z].x,q[z].y);
- printf("%.5lf %.5lf\n",q[x].x,q[x].y);
- printf("%.5lf %.5lf\n",q[y].x,q[y].y);
- }
- else{
- sort(q+1,q+1+4);
- printf("%.5lf %.5lf\n",q[1].x,q[1].y);
- printf("%.5lf %.5lf\n",q[3].x,q[3].y);
- printf("%.5lf %.5lf\n",q[4].x,q[4].y);
- printf("%.5lf %.5lf\n",q[2].x,q[2].y);
- }
- }
- int main(){
- // freopen("4.in","r",stdin);
- int n=In();
- for(int i=1;i<=n;++i) scanf("%lf%lf",&poi[i].x,&poi[i].y);
- n=ConvexHull(poi,n,p); int w,x,y,z; w=x=y=z=1;
- for(int i=2;i<=n;++i){
- if(p[i].y<p[w].y) w=i;
- if(p[i].y>p[x].y) x=i;
- if(p[i].x<p[y].x) y=i;
- if(p[i].x>p[z].x) z=i;
- }
- p[n+1]=p[1]; double ans=1e9;
- for(int i=1;i<=n;++i){
- while(Dis(p[x],p[w],p[w+1])<Dis(p[x+1],p[w],p[w+1])) x=x%n+1;
- while(dcmp(Dot(p[y+1]-p[y],p[w+1]-p[w]))<0) y=y%n+1;
- while(dcmp(Dot(p[z+1]-p[z],p[w+1]-p[w]))>0) z=z%n+1;
- double S=Dis(p[x],p[w],p[w+1])*Dot(p[z]-p[y],p[w+1]-p[w])/Len(p[w+1]-p[w]);
- if(ans>S){
- Vector vec=Rotate(p[w+1]-p[w],Pi/2);
- q[1]=Get_Poi(p[y],p[w+1],p[w]);
- q[2]=Get_Poi(p[z],p[w+1],p[w]);
- q[3]=Get_Poi(p[x],q[1],q[1]+vec);
- q[4]=Get_Poi(p[x],q[2],q[2]+vec);
- ans=S;
- }
- w=w%n+1;
- }
- printf("%.5lf\n",ans); print();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2988704.html