misschuer

常用链接

统计

积分与排名

百事通

最新评论

ZOJ 3194 Coverage

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MAX 1002
 5 
 6 bool comp (double a , double b)
 7 {
 8   return a < b;
 9 }
10 
11 int main()
12 {
13   double x[ MAX ] , y[ MAX ] , h[ MAX ];
14 
15   bool visited[ MAX ];
16 
17    int t , n , rear , i , j , index;
18 
19    cin >> t;
20    while (t --)
21    {
22      memset (visited , true , sizeof (visited));
23      cin >> n;
24      for (i = 1 ; i <= n ; ++ i)
25          cin >> x[ i ] >> y[ i ];
26      sort (x + 1 , x + n + 1 , comp);
27      sort (y + 1 , y + n + 1 , comp);
28      rear = n;
29   
30      x[ 0 ] = x[ 1 ];
31 
32      x[n + 1= x[ n ];
33  
34      for (i = 1 ; i <= n ; ++ i)
35      {
36          double max = 0;
37        for (j = 1 ; j <= n ; ++ j)
38        {
39          if (max < x[j + 1- x[j - 1&& visited[ j ])
40          {
41            max = x[j + 1- x[j - 1];
42            index = j;
43          }
44        }
45        h[ index ] = y[ rear ];
46        rear --;
47        visited[ index ] = false;
48      }
49   
50      double sum = 0;
51 
52      for (i = 1 ; i < n ; ++ i)
53        sum += (x[i + 1- x[ i ]) * (h[ i ] + h[i + 1]);
54 
55      sum /= 2;
56 
57      printf ("%.1f\n" , sum);
58    }
59    return 0;
60 }
61 
62 

posted on 2009-05-03 19:33 此最相思 阅读(292) 评论(3)  编辑 收藏 引用

评论

# re: ZOJ 3194 Coverage 2009-05-03 19:34 Wpl

加油......  回复  更多评论   

# re: ZOJ 3194 Coverage [未登录] 2009-05-06 09:42 noname

请问下 这题的 题目是什么意思呢?  回复  更多评论   

# re: ZOJ 3194 Coverage 2009-05-11 18:42 GY

排列Y使得线段下面的面积最大  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理