首页 > ACM题库 > HDU-杭电 > hdu 2528 Area-计算几何-[解题报告]C++
2014
02-09

hdu 2528 Area-计算几何-[解题报告]C++

Area

问题描述 :

电子科大清水河校区是电子科大大力兴建的未来主校区,于07年秋正式迎接学生入住,目前有07、08级本科生及部分研究生在此校区学习、生活。
清水河校区位于成都高新西区的中部地带,占地约3128亩。从空中看,新校区的整体像一个长方形,南北长,东西窄。一条水渠从西北角的顶点注入,笔直的延伸到南面围墙的大概三分之一分点的地方,由此流出学校。位于这条水渠和西墙之间的是研究院,最南面的是学术交流中心和接待中心。
在本题中,假设清水河校区是一个凸多边形,水渠是一条直线,要求给出清水河校区被水渠分割成的两部分的面积。

输入:

输入包含多组数据。每组数据第一行是一个整数N(3<=N<=20),表示清水河校区的边数,N=0表示输入结束。随后有N行,每行有两个整数X,Y(0<=X,Y<=10000),按顺时针顺序给出清水河校区的每个顶点的坐标。最后一行包含四个整数X0,Y0,X1,Y1,(0<= X0,Y0,X1,Y1<=10000),表示水渠上的两个点的(X0,Y0),(X1,Y1)的坐标,保证这两个点一定不会重合,同时保证水渠一定穿过清水河校区。

输出:

输入包含多组数据。每组数据第一行是一个整数N(3<=N<=20),表示清水河校区的边数,N=0表示输入结束。随后有N行,每行有两个整数X,Y(0<=X,Y<=10000),按顺时针顺序给出清水河校区的每个顶点的坐标。最后一行包含四个整数X0,Y0,X1,Y1,(0<= X0,Y0,X1,Y1<=10000),表示水渠上的两个点的(X0,Y0),(X1,Y1)的坐标,保证这两个点一定不会重合,同时保证水渠一定穿过清水河校区。

样例输入:

4
0 0
0 100
100 100
100 0
10 0 15 5
0

样例输出:

5950 4050

提示:
对于一个顺时针给出的多边形,如果它的顶点坐标依次是(xi,yi),0<=i<n,则它的面积为:
     
其中xn=x0,yn=y0

题意:

给定一个凸多边形和一条直线

求这个多边形被切割后的面积

对于代码中的

d1=dblcmp(s1=cross( p.node[i],s,e ));//跨立
d2=dblcmp(s2=cross( p.node[i+1],s,e ));//跨立

不是很理解。。。求指教

#include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 const double eps=1e-8;
 const int maxn = 505;
 struct point{
     double x,y;
 };
 struct ploy{
     point node[ maxn ];
     int n;
 };
 point left,right,s;
 ploy p,p1,p2;
 
 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);
 }
 
 double ploy_area( ploy res ){
     double ans=0;
     res.node[ res.n ]=res.node[0];
     for( int i=0;i<res.n;i++ ){
         ans+=cross( s,res.node[i],res.node[i+1] );
     }
     return ans;
 }
 
 int dblcmp(double a) {return a<-eps?-1:a>eps?1:0;}
 
 ploy cut( ploy p,point s,point e ){
     point tmp;
     ploy bb;
     int cnt=0;
     for( int i=0;i<p.n;i++ ){
         int d1,d2;
         double s1,s2;
         d1=dblcmp(s1=cross( p.node[i],s,e ));//跨立
         d2=dblcmp(s2=cross( p.node[i+1],s,e ));//跨立
         if( d1>=0 ){
             bb.node[ cnt ]=p.node[ i ];
             cnt++;
         }
         if( d1*d2<0 ){
             tmp.x=(s2*p.node[i].x-s1*p.node[i+1].x)/(s2-s1);
             tmp.y=(s2*p.node[i].y-s1*p.node[i+1].y)/(s2-s1);
             bb.node[ cnt ]=tmp;
             cnt++;
         }
     }
     bb.n=cnt;
     bb.node[ cnt ]=bb.node[ 0 ];
     return bb;
 }
 
 int main(){
     while( scanf("%d",&p.n),p.n ){
         for( int i=0;i<p.n;i++ ){
             scanf("%lf%lf",&p.node[ i ].x,&p.node[ i ].y);
         }
         p.node[ p.n ]=p.node[ 0 ];
         scanf("%lf%lf%lf%lf",&left.x,&left.y,&right.x,&right.y);
         s.x=s.y=0;
         p1=cut( p,left,right );
         p2=cut( p,right,left );
         int res1,res2;
         res1=int(fabs(ploy_area( p1 ))/2+0.5);
         res2=int(fabs(ploy_area( p2 ))/2+0.5);
         printf("%d %d\n",res1>res2?res1:res2,res1>res2?res2:res1);
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/justforgl/archive/2013/02/13/2910824.html


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  5. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢