給定一組點(diǎn)集，求至多選四點(diǎn)，使其所圍成的面積最大。
剛開始四重循環(huán)，直接超時(shí)掉。后來聽說要用到旋轉(zhuǎn)卡殼，且是在求三角形面積基礎(chǔ)上求四邊形面積的。在AC了一道旋轉(zhuǎn)卡殼法求最大三角形面積后，終于把這道給A了。
本題可以把四邊形分為兩個三角形的并，再用
旋轉(zhuǎn)卡殼法
分別求出這兩個三角形的最大面積。
如下圖所示，固定i，j點(diǎn)，分別找到這樣的h，k點(diǎn)使三角形ijk和三角形ijh面積都最大。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include <algorithm>
#include<math.h>
using namespace std;
int num,top;
struct Point
{
?int x,y;
?bool operator < (const Point a)const
?{
??return y<a.y||(y==a.y&&x<a.x);
?}
}s[1005],res[1005];
bool multi(Point o,Point a,Point b)
{
?return (b.x-o.x)*(a.y-o.y)>=(a.x-o.x)*(b.y-o.y);
}
int graham(Point s[],int n,Point res[])
{
?sort(s,s+n);
?int len,top=1;
?if(n==0)return 0;
?res[0]=s[0];
?if(n==1)return 1;
?res[1]=s[1];
?if(n==2)return 2;
?res[2]=s[2];
?for(int i=2;i<n;i++)
?{
??while(top&&multi(res[top-1],res[top],s[i]))top--;
??res[++top]=s[i];
?}
?len=top;
?res[++top]=s[n-2];
?for(int i=n-3;i>=0;i--)
?{
??while(top!=len&&multi(res[top-1],res[top],s[i]))top--;
??res[++top]=s[i];
?}
?return top;
}
int Area(Point p1,Point p2,Point p3)
{
?? ?return abs((p1.x*p2.y-p1.y*p2.x)+(p2.x*p3.y-p2.y*p3.x)+(p3.x*p1.y-p3.y*p1.x));
}
int MAX(int a,int b)
{
?? ?if(a>b)
?? ?return a;
?? ?else
?? ?return b;
}
int main()
{
?? ?int aa=1,cas,n,i,j,h,k,top,minx=10005,miny=10005;
?? ?int max1,max2,area,ans,ans1;
?? ?scanf("%d",&cas);
?? ?while(cas--)
?? ?{
?? ?ans=0;minx=10005;miny=10005;
?? ?scanf("%d",&n);
?? ?for(i=0;i<n;i++)
?? ? ? ? scanf("%d%d",&s[i].x,&s[i].y);
?? ? top=graham(s,n,res);
?? ? if(top==0||top==1||top==2)
?? ? ? ? ?ans=0;
?? ? else if(top==3)
?? ? ? ? ?ans=Area(res[0],res[1],res[2]);
?? ? else if(top==4)
?? ? ? ? ?ans=Area(res[0],res[1],res[2])+Area(res[0],res[3],res[2]); ? ?
?? ? else
?? ? {
?? ? for(i=0;i<top;i++)
?? ? {
?? ? ? ? ?j=(i+2)%top;
?? ? ? ? ?k=(i+1)%top;
?? ? ? ? ?h=(j+1)%top;
?? ? ? ? ?while(Area(res[i],res[j],res[k+1])>Area(res[i],res[j],res[k]))
?? ? ? ? ? ? ? k=(k+1)%top;
?? ? ? ? ?max1=Area(res[i],res[j],res[k]);
?? ? ? ? ?while(Area(res[i],res[j],res[h+1])>Area(res[i],res[j],res[h]))
?? ? ? ? ? ? ? h=(h+1)%top;
?? ? ? ? ?max2=Area(res[i],res[j],res[h]);
?? ? ? ? ?ans1=0;
?? ? ? ? ?while(max1+max2>ans1)
?? ? ? ? ?{?
?? ? ? ? ? ? ? j=(j+1)%top;
?? ? ? ? ? ? ? ans1=max1+max2;
?? ? ? ? ? ? ? while(Area(res[i],res[j],res[k+1])>Area(res[i],res[j],res[k]))
?? ? ? ? ? ? ? ? ? k=(k+1)%top;
?? ? ? ? ? ? ? max1=Area(res[i],res[j],res[k]);
?? ? ? ? ? ? ? while(Area(res[i],res[j],res[h+1])>Area(res[i],res[j],res[h]))
?? ? ? ? ? ? ? ? ? h=(h+1)%top; ? ? ? ? ? ? ??
?? ? ? ? ? ? ? max2=Area(res[i],res[j],res[h]);
?? ? ? ? ? ? ?
?? ? ? ? ?}
?? ? ? ? ?ans=MAX(ans,ans1);
?? ? }
?? ? }
?? ? printf("Case #%d: %d\n",aa++,ans);
?? ? }
?? ? //system("pause");
?? ? return 0;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
