2014
01-05

# 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 ;
}

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