POJ 1151 Atlantis（离散化）

题意：就是给你n个矩形的最左下角和最右上角的点的坐标，然后将这n个矩形的面积求出来。

思路：离散化求矩形面积并。离散化具体介绍。将横纵坐标离散开来分别存，然后排序，也可以按照黑书上411页写的两个算法中，有一个说是用二分，效率比较好，不过我用的不是二分，而是普通的循环查找。

 #include<iostream>

 #include <algorithm>

 #include <string.h>

 #include <stdio.h>

 using namespace std;

 double x[],y[],s[][];

 int flag[][];

 int t,cas =  ;

 double sum;

 int main()

 {

     while(~scanf("%d",&t))

     {

         if(t == ) break;

         int k =  ;

         sum = 0.0 ;

         memset(flag,,sizeof(flag));

         for(int i =  ; i <= n ; i++)

         {

             cin>>s[i][]>>s[i][]>>s[i][]>>s[i][];

             x[k] = s[i][];

             y[k] = s[i][];

             k++;

             x[k] = s[i][];

             y[k] = s[i][];

             k++;

         }

         sort(x,x+*n);

         sort(y,y+*n);

         for(k =  ; k <= n ; k++)

         {

             int a,b,c,d;

             for(a =  ; a < *n ; a++)

                 if(x[a] == s[k][]) break;

             for(b =  ; b < *n ; b++)

                 if(x[b] == s[k][]) break;

             for(c =  ; c < *n ; c++)

                 if(y[c] == s[k][]) break;

             for(d =  ; d < *n ; d++)

                 if(y[d] == s[k][]) break;

             for(int i = a ; i < b ; i++)

                 for(int j = c ; j < d ; j++)

                     flag[i][j] =  ;

         }

         for(int i =  ; i < *t ; i++)

             for(int j =  ; j < *t ; j++)

                 if(flag[i][j])

                     sum+=(x[i+]-x[i])*(y[j+]-y[j]);

         printf("Test case #%d\n",cas++);

         printf("Total explored area: %.2f\n\n",sum);

     }

     return ;

 }

巴特西

POJ 1151 Atlantis（离散化）

最新文章

热门文章