首页 > ACM题库 > HDU-杭电 > hdu 2306 Kingdom-计算几何-[解题报告]C++
2014
01-05

hdu 2306 Kingdom-计算几何-[解题报告]C++

Kingdom

问题描述 :

King Kong is the feared but fair ruler of Transylvania. The kingdom consists of two cities and N < 150 towns, with nonintersecting roads between some of them. The roads are bidirectional, and it takes the same amount of time to travel them in both directions. Kong has G < 353535 soldiers.
Due to increased smuggling of goat cheese between the two cities, Kong has to place his soldiers on some of the roads in such a way that it is impossible to go from one city to the other without passing a soldier. The soldiers must not be placed inside a town, but may be placed on a road, as close as Kong wishes, to any town. Any number of soldiers may be placed on the same road. However, should any of the two cities be attacked by a foreign army, the king must be able to move all his soldiers fast to the attacked city. Help him place the soldiers in such a way that this mobilizing time is minimized.
Note that the soldiers cannot be placed in any of the cities or towns. The cities have ZIP-codes 95050 and 104729, whereas the towns have ZIPcodes from 0 to N – 1. There will be at most one road between any given pair of towns or cities.

输入:

The input contains several test cases. The first line of each test case is N, G and E, where N and G are as defined above and E < 5000 is the number of roads. Then follow E lines, each of which contains three integers: A and B, the ZIP codes of the endpoints, and φ, the time required to travel the road,φ < 1000. The last line of the input is a line containing a single 0.

输出:

The input contains several test cases. The first line of each test case is N, G and E, where N and G are as defined above and E < 5000 is the number of roads. Then follow E lines, each of which contains three integers: A and B, the ZIP codes of the endpoints, and φ, the time required to travel the road,φ < 1000. The last line of the input is a line containing a single 0.

样例输入:

4 2 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 1 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 2 7
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
2 1 5
0

样例输出:

2.5
Impossible
3.0

题目链接~~>

                   这题求的是任意多边形的面积。

(1).用向量叉乘:A(x1,y1), B(x2,y2) , C(x3,y3) . AB(x2-x1,y2-y1),AC(x3-x1,y3-x3)  然后求ABxAC(求AB AC的行列式)然后将结果的绝对值除以2.

          求多边形面积不用绝对值。

(2).补充:海伦公式:AB=a BC =b AC=c p=(a+b+c)/2   面积S=sqrt(p*(p-a)*(p-b)*(p-c)).

代码:

#include<stdio.h>
#include<math.h>
int main()
{
    int n ;
    int x1,x2,x3,y1,y2,y3 ;
    while(scanf("%d",&n)!=EOF)
     {
         if(n==0)
              break ;
         scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
         double sum=0 ;
         for(int i=2;i<n;i++)
          {
              scanf("%d%d",&x3,&y3);
              sum=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
              printf("%.1lf\n",sum) ;
              x2=x3 ;
              y2=y3 ;
          }
        printf("%.1lf\n",sum/2.0) ;
     }
     return 0 ;
}

 

解题转自:http://blog.csdn.net/nyist_zxp/article/details/11962951


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。