#UVa:920-Sunny Mountains

灆洢 2012-01-19 08:05:44

從X的最後面一個一個山峰搜回來,遇到山峰比之前還高就要進行加線段的動作,如此做完即可得解。

C++(0.008)

/*******************************************************/
/* UVa 920 Sunny Mountains                             */
/* Author: Maplewing [at] knightzone.studio            */
/* 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) );
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料