1382 - Distant Galaxy（技巧枚举+离散化） - c++编程基础

You are observing a distant galaxy using a telescope above the Astronomy Tower, and you think that a rectangle drawn in that galaxy whose edges are parallel to coordinate axes and contain maximum star systems on its edges has a great deal to do with the mysteries of universe. However you do not have the laptop with you, thus you have written the coordinates of all star systems down on a piece of paper and decide to work out the result later. Can you finish this task

$\epsfbox{p3694.eps}$

Input

There are multiple test cases in the input file. Each test case starts with one integer N , (1 $\le$ N $\le$ 100) , the number of star systems on the telescope. N lines follow, each line consists of two integers: the X and Y coordinates of the K -th planet system. The absolute value of any coordinate is no more than 10⁹ , and you can assume that the planets are arbitrarily distributed in the universe.

N = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, output the maximum value you have found on a single line in the format as indicated in the sample output.

Sample Input

Sample Output

Case 1: 7

题意：给定一些坐标的点，然后求出一个矩形上面点数最多

思路：由于坐标很大并且有负数，所以利用map离散化，然后每次枚举上边界和下边界，然后从左边界一直往右边界推，类似前缀求和思想维护一个最小值即可。原来没特判点全在一条直线的情况一直WA。。坑啊

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
      #include 
      
        #define max(a,b) ((a)>(b) (a):(b)) #define min(a,b) ((a)<(b) (a):(b)) #define INF 0x3f3f3f3f using namespace std; const int N = 105; int n, x[N], y[N], xn, yn, g[N][N], flag1, flag2; vector
       
         xp[N], yp[N]; map
        
          xv, yv; struct Point { int x, y; } p[N]; bool cmp(Point a, Point b) { return a.y < b.y; } void init() { flag1 = flag2 = 0; int j; xn = 1; yn = 1; memset(g, 0, sizeof(g)); memset(xp, 0, sizeof(xp)); memset(yp, 0, sizeof(yp)); xv.clear(); yv.clear(); for (j = 0; j < n; j++) { scanf("%d%d", &p[j].x, &p[j].y); } for (j = 1; j < n; j++) { if (p[j].x != p[j - 1].x) flag1 = 1; if (p[j].y != p[j - 1].y) flag2 = 1; } sort(p, p + n, cmp); for (int i = 0; i < n; i++) { int xx = p[i].x, yy = p[i].y; if (!xv[xx]) { xv[xx] = xn; x[xn++] = xx; } if (!yv[yy]) { yv[yy] = yn; y[yn++] = yy; } g[xv[xx]][yv[yy]] = 1; xp[xv[xx]].push_back(yy); yp[yv[yy]].push_back(xx); } } int solve() { if (flag1 == 0 || flag2 == 0) return n; int ans = 0; for (int i = 1; i < xn; i++) { for (int j = i + 1; j < xn; j++) { int Min = INF; for (int k = 1; k < yn; k++) { int s = 0, h = 0; for (int x1 = 0; x1 < xp[i].size(); x1++) { if (xp[i][x1] < y[k]) h++; } for (int x2 = 0; x2 < xp[j].size(); x2++) { if (xp[j][x2] < y[k]) h++; } for (int y1 = 0; y1 < yp[k].size(); y1++) { int up = max(x[i], x[j]); int down = min(x[i], x[j]); if (yp[k][y1] < up && yp[k][y1] > down) s++; } ans = max(ans, h + s - Min + g[i][k] + g[j][k]); Min = min(Min, h - s); } } } return ans; } int main() { int cas = 0; while (~scanf("%d", &n) && n) { init(); printf("Case %d: %d\n", ++cas, solve()); } return 0; }