写了一天了,球球各路神仙了……会给关注QwQ
查看原帖
写了一天了,球球各路神仙了……会给关注QwQ
477755
yuzu1207_pooh楼主2022/8/15 15:48

Rt,死活只有10pts,球球救救了……

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define ll long long
#define maxn 50005
using namespace std;
int n,m,top;
double myans;
struct emm {
	double x,y;
	emm operator +(const emm &oth) {return (emm){x+oth.x,y+oth.y};}
	emm operator -(const emm &oth) {return (emm){x-oth.x,y-oth.y};}
	double operator *(const emm&oth) {return x*oth.y-oth.x*y;}
	double operator ^(const emm &oth) {return x*oth.x+y*oth.y;}
	friend inline emm rot(const emm &t) {return (emm){t.y,-t.x};}
	emm operator *(double d) {return (emm){x*d,y*d};}
}p[maxn],s[maxn],ans[5];
inline double check(emm a1,emm a2,emm b1,emm b2) {
	return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
inline double dis(emm p1,emm p2) {return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);}
inline bool cmp(emm p1,emm p2) {
	double tmp=check(p[1],p1,p[1],p2);
	if(fabs(tmp)>eps)return tmp>eps;
	return dis(p1,p[1])<dis(p2,p[1])-eps;
}
inline void add(int x,int y) {
	p[++m]=(emm){x,y};
	if(p[m].y<p[1].y)swap(p[1],p[m]);
	if(p[m].y==p[1].y&&p[m].x<p[1].x)swap(p[1],p[m]);
}
void Graham() {
	sort(p+2,p+m+1,cmp);
	s[++top]=p[1];
	for(int i=2;i<=m;i++){
		while(top>1&&check(s[top-1],s[top],s[top],p[i])<eps)top--;
		s[++top]=p[i];
	}
	s[top+1]=p[1];
}
struct node {
	emm u,l,r;
}a[maxn];
inline double S(emm aa,emm bb,emm cc) {return check(bb,aa,cc,aa);}
inline double pho(emm aa,emm bb,emm cc,emm dd) {return (bb-aa)^(dd-cc);}
inline int nxt(int x) {
	if(++x>top)x=1;
	return x;
}
inline int pre(int x) {
	if(--x<1)x=top;
	return x;
}
void rotat1() {
	int j=3,k=2;
	for(int i=1;i<=top;i++){
		while(nxt(j)!=i&&S(s[i],s[i+1],s[j])<S(s[i],s[i+1],s[nxt(j)])-eps)j=nxt(j);
		a[i].u=s[j];
		while(nxt(k)!=i&&pho(s[i],s[i+1],s[k],s[nxt(k)])>eps)k=nxt(k);
		a[i].r=s[k];
	}
}
void rotat2() {
	int j=top;
	for(int i=top;i;i--){
		while(pre(j)!=i+1&&pho(s[i],s[i+1],s[j],s[pre(j)])<eps)j=pre(j);
		a[i].l=s[j];
	}
}
void solve() {
	Graham();
	rotat1();rotat2();
	myans=(double)inf*inf;
	for(int i=1;i<=top;i++){
		double aa=sqrt(dis(s[i+1],s[i]));
		emm ab=s[i+1]-s[i];
		double bb=(ab^(a[i].l-s[i]))/aa,cc=(ab^(a[i].r-s[i+1]))/aa;
		bb=fabs(bb);cc=fabs(cc);
		double len=aa+bb+cc;
		double he=ab*(a[i].u-s[i])/aa;
		he=fabs(he);
		double ss=len*he;
		if(ss<myans-eps){
			myans=ss;
			ans[0]=s[i+1]+ab*(cc/aa);
			ans[1]=ans[0]+rot(ab)*(-he/aa);
			ans[2]=ans[1]+rot(ans[1]-ans[0])*(-len/he);
			ans[3]=ans[2]+rot(ans[2]-ans[1])*(-he/len);
		}
	}
	printf("%.5lf\n",myans);
	int id=1;
	for(int i=1;i<4;i++)
		if(ans[i].y<ans[id].y-eps||(fabs(ans[i].y-ans[id].y)<eps&&ans[i].x<ans[id].x-eps))id=i;
	for(int i=0;i<4;i++){
		double x=ans[(i+id)%4].x,y=ans[(i+id)%4].y;
		if(fabs(x)<1e-5)x=0;
		if(fabs(y)<1e-5)y=0;
		printf("%.5lf %.5lf\n",x,y);
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf %lf",&x,&y);
		add(x,y);
	}
	solve();
	return 0;
}
2022/8/15 15:48
加载中...