题目链接P3187 [HNOI2007]最小矩形覆盖

rt，球球帮忙看看(

代码可能很丑

#include <bits/stdc++.h>
struct stack {
	int the_stack[50001],sum=0;
	inline int top() { return the_stack[sum-1]; }
	inline int pop() { return sum ? the_stack[--sum] : -1; }
	inline int push(int x) { the_stack[sum++]=x; }
	inline int operator[](const int &x) const{
		return the_stack[x-1];
	}
	inline void clear() { sum=0; }
}st;
inline double read() {
	double x,k=1;char ch;bool f;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	if(ch=='.') for(;isdigit(ch=getchar());k/=10.0,x+=k*(ch-48));
	return f?-x:x;
}
inline void print(long long x,char las) {
	if(!x) {
		putchar('0'),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[23],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ;
}
struct node {
	double x,y;
	inline void output() {
		printf("%.5lf %.5lf\n",x,y);
		return ;
	} 
	inline double len() {
		return sqrt(x*x+y*y);
	}
	inline bool operator!=(const node &ls) const {
		return x!=ls.x || y!=ls.y;
	}
	inline bool operator<(const node &ls) const {
		return ls.x!=x ? x<ls.x : y<ls.y;
	} 
	inline node operator+(const node &ls) const {
		return {x+ls.x,y+ls.y};
	}
	inline void operator+=(const node &ls) {
		x+=ls.x;
		y+=ls.y;
		return ;
	}
	inline node operator-(const node &ls) const {
		return {x-ls.x,y-ls.y};
	}
	inline void operator-=(const node &ls) {
		x-=ls.x;
		y-=ls.y;
		return ;
	}
	inline node operator*(const double &ls) const {
		return {x*ls,y*ls};
	}
	inline void operator*=(const double &ls) {
		x*=ls;
		y*=ls;
		return ;
	}
	inline node operator/(const double &ls) const {
		return {x/ls,y/ls};
	}
	inline void operator/=(const double &ls) {
		x/=ls;
		y/=ls;
		return ;
	}
	inline double operator*(const node &ls) const {
		return x*ls.y-y*ls.x;
	}
	inline double operator*=(const node &ls) const {
		return x*ls.x+y*ls.y;
	}
}nd[50001],the_line,td[4];
int n=read();
double ans=1e15;
inline bool cmp(node a,node b) {
	return a.y<b.y;
}
int main() {
	int now=2,th_l,th_r=1;
	for(int i=1;i<=n;i++) scanf("%lf%lf",&nd[i].x,&nd[i].y);
	std::sort(nd+1,nd+n+1);
	for(int i=1;i<=n;i++) {
		while(st.sum>=2 && (nd[i]-nd[st.top()])*(nd[st.top()]-nd[st[st.sum-1]])>=0) st.pop();
		st.push(i);
	}
	th_l=st.sum;
	for(int i=n-1;i>=1;i--) {
		while(st.sum>=2 && (nd[i]-nd[st.top()])*(nd[st.top()]-nd[st[st.sum-1]])>=0) st.pop();
		st.push(i);
	}
	int as=st.sum-1;
//	std::cout<<st.sum<<'\n';
	for(int i=1;i<st.sum;i++) {
		node line=nd[st[i+1]]-nd[st[i]];double ll=line.len();
		while(abs(line*(nd[st[now]]-nd[st[i]]))<abs(line*(nd[st[now%as+1]]-nd[st[i]]))) now=now%as+1;
		while((line*=(nd[st[th_l]]-nd[st[i]])/ll)-(line*=(nd[st[th_l%as+1]]-nd[st[i]])/ll)>1e-6) th_l=th_l%as+1;
		while((line*=(nd[st[th_r]]-nd[st[i+1]])/ll)-(line*=(nd[st[th_r-1 ? th_r-1 : as]]-nd[st[i+1]])/ll)<-1e-6) th_r=th_r-1 ? th_r-1 : as;
		double xx=abs(line*=(nd[st[th_l]]-nd[st[i]])/ll)+abs(line*=(nd[st[th_r]]-nd[st[i+1]])/ll)+ll,yy=abs(line*(nd[st[now]]-nd[st[i]]))/ll;
		if(xx*yy<ans) {
//			nd[st[now]].output();
//			nd[st[th_l]].output();nd[st[th_r]].output();
//			printf("%.5lf ",xx);printf("%.5lf\n",yy);
			ans=xx*yy;
			the_line=line;
			node cz;
			cz.x=1;
			cz.y=-cz.x*line.x/line.y;
			cz/=cz.len();cz*=(line*(nd[st[now]]-nd[st[i]]))/ll;cz*=-1;
			td[0]=nd[st[i+1]]+line/ll*(line*=(nd[st[th_r]]-nd[st[i+1]])/ll);
			td[1]=td[0]+cz;
			td[2]=nd[st[i]]+line/ll*(line*=(nd[st[th_l]]-nd[st[i]])/ll);
			td[3]=td[2]+cz;
		}
	}
	printf("%.5lf\n",ans);
	st.clear();
	std::sort(td,td+4,cmp);
	node fs=td[0];
	std::sort(td,td+4);
	for(int i=0;i<4;i++) {
		while(st.sum>=2 && (td[i]-td[st.top()])*(td[st.top()]-td[st[st.sum-1]])>=0) st.pop();
		st.push(i);
	}
	for(int i=3;i>=0;i--) {
		while(st.sum>=2 && (td[i]-td[st.top()])*(td[st.top()]-td[st[st.sum-1]])>=0) st.pop();
		st.push(i);
	}
	stack ts;
	for(int i=0;i<4;i++) {
		if(fs!=td[st.top()]) ts.push(st.pop());
		else {
			td[st.pop()].output();
			while(ts.sum) td[ts.pop()].output();
		}
	}
	while(ts.sum) td[ts.pop()].output();
//	printf("%.5lf",3.0*sqrt(2));
	return 0;
}