首页 > ACM题库 > HDU-杭电 > HDU 3934-Summer holiday-计算几何-[解题报告]HOJ
2015
04-14

HDU 3934-Summer holiday-计算几何-[解题报告]HOJ

Summer holiday

问题描述 :

Summer holiday was coming! Xiaomao went back to his hometown where he yearn day and night, his hometown has picturesque scenery. There is a big forest beside his village. There are n trees in the forest.
Now they want to across the forest with a rope (the rope won’t cross). Try to find 3 trees in this tree on the rope which can make the area of the surrounded largest. Work out the area of it.

输入:

The input will consist of several test cases. The first line contains a positive integer N(3<=N<=10^6), the number of trees, followed N lines, each gives the (xi, yi ) coordinates.

输出:

The input will consist of several test cases. The first line contains a positive integer N(3<=N<=10^6), the number of trees, followed N lines, each gives the (xi, yi ) coordinates.

样例输入:

4
0 0
1 1
0 1
1 0

样例输出:

0.50

题意:

给一些点,任选任选三个构成三角形,求这个三角形的最大面积。

 

题解:
旋转卡壳,水题了。。

n^2明显的过不了的,但是数据水,能过。

有没有nlogn的算法啊??

 

 

 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 #include <cmath>
 
 #define N 100010
 #define EPS 1e-7
 
 using namespace std;
 
 struct PO
 {
     double x,y;
 }p[N],stk[N],o;
 
 int top,n;
 double ans;
 
 inline PO operator -(PO a,PO b)
 {
     PO c;
     c.x=a.x-b.x;
     c.y=a.y-b.y;
     return c;
 }
 
 inline double cross(PO a,PO b,PO c)
 {
     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
 }
 
 inline int dc(double x)
 {
     if(x>EPS) return 1;
     else if(x<-EPS) return -1;
     return 0;
 }
 
 inline bool cmp(const PO &a,const PO &b)
 {
     if(dc(a.x-b.x)==0) return a.y<b.y;
     return a.x<b.x;
 }
 
 inline double getangle(PO &a,PO &b,PO &c,PO &d)
 {
     return cross(o,b-a,d-c);
 }
 
 inline void read()
 {
     for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
 }
 
 inline void graham()
 {
     sort(p+1,p+1+n,cmp);
     top=-1;
     stk[++top]=p[1]; stk[++top]=p[2];
     for(int i=3;i<=n;i++)
     {
         while(top>=1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
         stk[++top]=p[i];
     }
     int tmp=top;
     for(int i=n-1;i>=1;i--)
     {
         while(top>=tmp+1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
         stk[++top]=p[i];
     }
 }
 
 inline void rotating_calipers()
 {
     ans=0.0;
     for(int i=0;i<top;i++)
     {
         int s=i+1;
         for(int j=i+1,k=1;k<top;k++,j=(j+1)%top)
         {
             if(s==j) s=(s+1)%top;
             while(s!=i&&dc(getangle(stk[i],stk[j],stk[s],stk[(s+1)%top]))>0) s=(s+1)%top;
             if(s!=i) ans=max(ans,0.5*fabs(cross(stk[i],stk[j],stk[s])));
         }
     }
 }
 
 inline void go()
 {
     graham();
     rotating_calipers();
     printf("%.2lf\n",ans);
 }
 
 int main()
 {
     while(scanf("%d",&n)!=EOF) read(),go();//HDU
     //while(scanf("%d",&n)&&n!=-1) read(),go();//POJ
     return 0;
 }

 

一个代码交两个OJ真是爽~

 

参考:http://www.cnblogs.com/proverbs/archive/2013/02/25/2932783.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环