題目描述

有一塊農(nóng)田，田地里安放上N個小木樁，木樁的占地面積忽略不計。選擇三個小木樁，使得三個小木樁的圍成的三角形占地面積最大。

輸入

第一行一個整數(shù)N(3<=n<=100)，便是木樁個數(shù)。

接下來N行，每行含有兩個整數(shù)xi和yi(-10000<=xi,yi<=10000)，表示第i個木樁的平面坐標(biāo)。

輸出

僅含有一個數(shù)，表示得到的農(nóng)田面積的最大值，結(jié)果保留一位小數(shù)。

樣例輸入

4 0?0 0?1 1?0 1?1

樣例輸出

0.5

實現(xiàn)代碼：

#include

#include

#include

#include

#include

using namespace std;

const int N=50005;

struct Point

{

double x,y;

};

Point stack[N];

Point p[N];

Point MinA;

int top;

double dist(Point A,Point B)

{

return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));

}

double cross(Point A,Point B,Point C)

{

return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);

}

bool cmp(Point a,Point b)

{

double k=cross(MinA,a,b);

if(k>0) return 1;

if(k<0) return 0;

return dist(MinA,a)

}

void Graham(int n)

{

int i;

for(i=1; i

if(p[i].y

swap(p[i],p[0]);

MinA=p[0];

sort(p+1,p+n,cmp);

stack[0]=p[0];

stack[1]=p[1];

top=1;

for(i=2; i

{

while(cross(stack[top-1],stack[top],p[i])<=0&&top>=1) --top;

stack[++top]=p[i];

}

}

double rotating_calipers(int n)

{

int j=1,k=0;

double ans=0;

for(int i=0;i

{

j=(i+1)%n;

k=(j+1)%n;

while(fabs(cross(stack[i],stack[j],stack[k]))

k=(k+1)%n;

while(j!=i&&k!=i)

{

ans=max(ans,fabs(cross(stack[i],stack[j],stack[k])));

while(fabs(cross(stack[i],stack[j],stack[k]))

k=(k+1)%n;

j=(j+1)%n;

}

}

return ans*0.5;

}

int main()

{

int n;

while(~scanf("%d",&n))

{

if(n==-1) break;

for(int i=0;i

scanf("%lf%lf",&p[i].x,&p[i].y);

if(n<3)

{

puts("0.00");

continue;

}

Graham(n);

top++;

if(top<3)

{

puts("0.0");

continue;

}

if(top==3)

{

printf("%.1lf\n",fabs(cross(stack[0],stack[1],stack[2]))/2);

continue;

}

printf("%.1lf\n",rotating_calipers(top));

}

return 0;

}

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的n个点组成多少个三角形Java,农田开发 NOJ （已知N个点选取3个求最大三角形面积问题）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。