首页 > 代码库 > UVa 920 - Sunny Mountains

UVa 920 - Sunny Mountains

题目:有一些山,在一个平面山,给你每个山峰的坐标,太阳从右边照过来,被照到的线段的长度和。

分析:计算几何、贪心。首先,按很坐标排序;然后,每次找到左边第一个比它高的山峰,

            求出对应的照射长度,求和即可。

说明:while(scanf("%d",&t))导致TLE,╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct pnode
{
	double x,y;
}point;
point P[100];

bool cmp( point a, point b )
{
	return a.x > b.x;
}

double dist( point a, point b )
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main()
{
	int T,N;
	while ( ~scanf("%d",&T) )
	while ( T -- ) {
		scanf("%d",&N);
		for ( int i = 0 ; i < N ; ++ i )
			scanf("%lf%lf",&P[i].x,&P[i].y);
		sort(P, P+N, cmp);
		
		double sums = 0.0;
		int    last = 0;
		for ( int i = 1 ; i < N ; ++ i )
			if ( P[i].y > P[last].y ) {
				sums += dist(P[i], P[i-1])*(P[i].y-P[last].y)/(P[i].y-P[i-1].y);
				last = i;
			}
		
		printf("%.2lf\n",sums);
	}
	return 0;
}