從X的最後面一個一個山峰搜回來,遇到山峰比之前還高就要進行加線段的動作,如此做完即可得解。
C++(0.008)
/*******************************************************/ /* UVa 920 Sunny Mountains */ /* Author: LanyiKnight [at] knightzone.org */ /* Version: 2012/01/19 */ /*******************************************************/ #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; struct Point{ double x; double y; Point( double, double ); }; Point::Point( double nx = 0.0, double ny = 0.0 ):x(nx),y(ny){} bool compare( Point, Point ); double length( Point, Point ); int main(){ int C, N; Point mountain[105]; double highest, line, temp, m, c; while( scanf( "%d", &C ) != EOF ){ for( int i = 0 ; i < C ; i++ ){ scanf( "%d", &N ); for( int j = 0 ; j < N ; j++) scanf( "%lf%lf", &(mountain[j].x), &(mountain[j].y) ); sort( mountain, mountain+N, compare ); highest = 0, line = 0; for( int j = 1 ; j < N ; j++ ){ if( mountain[j].y > highest ){ m = (mountain[j].y-mountain[j-1].y)/(mountain[j].x-mountain[j-1].x); c = mountain[j].y - m*mountain[j].x; temp = (highest-c)/m; line += length( mountain[j], Point( temp, highest ) ); highest = mountain[j].y; } } printf( "%.2lf\n", line ); } } return 0; } bool compare( Point a, Point b ){ return a.x > b.x; } double length( Point a, Point b ){ return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ); }