點擊打開鏈接uva 1382

題意：給出平面上的n個點，找出一個矩形，使得邊界上含有盡量多的點
思路：
1 很清楚，如果輸入的n個點在同一行或者同一列的話那么ans = n。還有一種情況就是n個點的橫坐標和縱坐標只有2種，那么這種情況ans = n。
2 對于這一題我們考慮的是枚舉矩形的上下邊界（縱坐標），然后利用其它的方法求左右邊界，見下圖

3 對于豎線i，我們用left[i]表示豎線左邊位于上下邊界的點數（不包括位于豎線i）, on[i]表示豎線上位于上下邊界之間的點數（和on2[i]的區別就是on[i]不統計位于上下邊界的點數），這樣給定左右邊界i和j的話，矩形邊界上的點數為left[j]+on2[j]+on[i]-left[i],當有邊界j確定的時候，on[i]-left[i]要最大
4 那么我們枚舉完上下邊界后，我們利用O(n)的時間去求left[] , on[] , on2[]，然后枚舉有邊界j，維護最大的on[i]-left[i]

代碼：

    
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;
struct Node{
    int x;
    int y;
    bool operator<(const Node& s)const{
        return x < s.x; 
    }
};
Node node[MAXN];
int n , numy[MAXN];

int solve(){
    sort(node , node+n);
    sort(numy , numy+n);
    int num = unique(numy , numy+n)-numy;
    if(num <= 2)//如果縱坐標最多只有2個那么ans = n
       return n;
    //枚舉上下界
    int miny , maxy , ans;
    int left[MAXN] , on[MAXN] , on2[MAXN];
    ans = 0;
    for(int i = 0 ; i < num ; i++){
       for(int j = i+1 ; j < num ; j++){
           miny = numy[i];
           maxy = numy[j];
           //求left , on , on2數組;
           int k = -1;
           memset(left , 0 , sizeof(left));
           memset(on , 0 , sizeof(on));
           memset(on2 , 0 , sizeof(on2));
           for(int t = 0 ; t < n ; t++){
              if(!t || node[t].x != node[t-1].x){
                 k++;
                 left[k] = k == 0 ? 0 : left[k-1]+on2[k-1]-on[k-1]; 
              }
              if(node[t].y > miny && node[t].y < maxy)
                 on[k]++;
              if(node[t].y >= miny && node[t].y <= maxy)
                 on2[k]++;
           }
           if(k <= 1)//如果橫坐標最多只有2個那么ans = n
              return n;
           int Max = 0;
           for(int t = 0 ; t <= k ; t++){
              ans = max(ans , left[t]+on2[t]+Max); 
              Max = max(Max , on[t]-left[t]); 
           }
       }
    }
    return ans;
}

int main(){
    int Case = 1;
    while(scanf("%d" , &n) && n){
         for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &node[i].x , &node[i].y); 
            numy[i] = node[i].y;
         }
         printf("Case %d: %d\n" , Case++ , solve());
    } 
    return 0;
}


  

uva 1382 - Distant Galaxy