平面上有4n个点求能够包含这些点的最小矩形面积下载_Word模板_5

is_153723

暂无简介

平面上有4n个点求能够包含这些点的最小矩形面积平面上有4n个点求能够包含这些点的最小矩形面积 #include #include #include #define eps 1e-8 #define N 50010 using namespace std; struct Point { double x,y; Point() {} Point(double x0,double y0):x(x0),y(y0) {} }p[N]; int con[N], cn, n; //n点的数量 struct Line { Point a,b; ...

平面上有4n个点求能够包含这些点的最小矩形面积 #include #include #include #define eps 1e-8 #define N 50010 using namespace std; struct Point { double x,y; Point() {} Point(double x0,double y0):x(x0),y(y0) {} }p[N]; int con[N], cn, n; //n点的数量 struct Line { Point a,b; Line() {} Line(Point a0,Point b0):a(a0),b(b0) {} }; double Xmult(Point o,Point a,Point b) { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } double Dmult(Point o,Point a,Point b) { return (a.x-o.x)*(b.x-o.x)+(a.y-o.y)*(b.y-o.y); } int Sig(double a) { return a<-eps?-1:a>eps; } double Dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int cmp(Point a,Point b) { double d=Xmult(p[0],a,b); if(d>0) return 1; if(d==0 && Dis(p[0],a)p[i].y || (p[ind].y==p[i].y) && p[ind].x>p[i].x) ind=i; swap(p[ind],p[0]); sort(p+1,p+n,cmp); con[0]=0; con[1]=1; cn=1; for(i=2; i0 && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0) cn--; con[++cn]=i; } int tmp=cn; for(i=n-2; i>=0; i--) { while(cn>tmp && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0) cn--; con[++cn]=i; } } double Solve() { int t,r,l; double ans=999999999; t=r=1; if(cn<3) return 0; for(int i=0; i0) t=(t+1)%cn; while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[r+1]])- Dmult(p[con[i]],p[con[i+1]],p[con[r]]) )>0) r=(r+1)%cn; if(!i) l=r; while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[l+1]])- Dmult(p[con[i]],p[con[i+1]],p[con[l]]) )<=0) l=(l+1)%cn; double d=Dis(p[con[i]],p[con[i+1]]); double tmp=Xmult(p[con[i]],p[con[i+1]],p[con[t]])* ( Dmult(p[con[i]],p[con[i+1]],p[con[r]])- Dmult(p[con[i]],p[con[i+1]],p[con[l]]) )/d/d; ans=min(ans,tmp); } return ans; } int main() { int i; int T, cas = 1; scanf("%d", &T); while(T --) { scanf("%d",&n); n *= 4; //点的数量 for(i=0; i

本文档为【平面上有4n个点求能够包含这些点的最小矩形面积】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

历史搜索

清空历史搜索

平面上有4n个点求能够包含这些点的最小矩形面积

热门搜索

历史搜索