平面上有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软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。