題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3934

題意：給出n個(gè)點(diǎn)，從中找出三個(gè)點(diǎn)使得面積最大。

思路：旋轉(zhuǎn)卡殼模板題：首先求凸包，在旋轉(zhuǎn)求最大面積。

#include <iostream> #include <stdio.h> #include <cmath> #include <algorithm> using namespace std;struct point {double x,y;point(){}point(double _x,double _y){x=_x;y=_y;}void get(){scanf("%lf%lf",&x,&y);} };const double EPS=1e-8; const int MAX=1000005; point p[MAX],q[MAX]; int n,m;int DB(double x) {if(x>EPS) return 1;if(x<-EPS) return -1;return 0; }double Dis(point a,point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }//判斷p在向量ab的哪一側(cè) //右側(cè)：返回正值 //左側(cè)：返回負(fù)值 //在向量ab上返回0 double cross(point a,point b,point p) {return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x); }int cmp(point a,point b) {double x=Dis(a,p[0]),y=Dis(b,p[0]);int flag=DB(cross(p[0],a,b));if(flag) return flag==1;return DB(x-y)<=0; }void Graham(point p[],int n,point q[],int &m) {point temp;int i,k=0,a,b;for(i=1;i<n;i++){a=DB(p[i].y-p[k].y);b=DB(p[i].x-p[k].x);if(a==-1||!a&&b==-1) k=i;}if(k!=0) temp=p[0],p[0]=p[k],p[k]=temp;sort(p+1,p+n,cmp);q[0]=p[0];q[1]=p[1];p[n]=p[0];m=2;for(i=2;i<=n;i++){while(m>1&&DB(cross(q[m-2],q[m-1],p[i]))<=0) m--;q[m++]=p[i];}m--; }double calMaxArea(point q[],int n) {if(n<3) return 0;double ans=0,temp;int t1=1,t2=2,i;q[n]=q[0];for(i=0;i<n;i++){while(DB(cross(q[t2+1],q[i],q[t1])-(temp=cross(q[t2],q[i],q[t1])))==1)t2=(++t2)%n;if(DB(temp-ans)==1) ans=temp;while(DB(cross(q[t2],q[i],q[t1+1])-(temp=cross(q[t2],q[i],q[t1])))==1)t1=(++t1)%n;if(DB(temp-ans)==1) ans=temp;}return ans/2; }int main() {while(scanf("%d",&n)!=-1){int i;for(i=0;i<n;i++) p[i].get();Graham(p,n,q,m);double ans=calMaxArea(q,m);printf("%.2lf\n",ans);}return 0; }

　　

總結(jié)

以上是生活随笔為你收集整理的HDU 3934 Summer holiday（凸包内接最大三角形）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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