uvalive3695Distant Galaxy

简介: 题意:给出平面上的n个点,找一个矩形,使得边界上包含尽量多的点。 代码: View Code 1 #include 2 #include 3 #include 4 #define DEBUG 5 using namespace std; 6 struct Z...

题意:给出平面上的n个点,找一个矩形,使得边界上包含尽量多的点。

代码:

View Code
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define DEBUG
 5 using namespace std;
 6 struct ZZ{
 7     int x, y;
 8     bool operator < (const ZZ& p) const{
 9         return x<p.x;
10     }
11 };
12 int max(int a, int b){
13     return a>b?a:b;
14 }
15 const int MAXN = 100 + 10;
16 ZZ p[MAXN];
17 int n, m, y[MAXN], on[MAXN], on2[MAXN], zl[MAXN];
18 
19 int solve(){
20     sort(p, p+n);
21     sort(y, y+n);
22     m = unique(y, y+n) - y;
23     if(m<=2) return n;
24     
25     int ans = 0;
26     for(int a=0; a<m; a++){
27         for(int b=a+1; b<m; b++){
28             int ymin = y[a];
29             int ymax = y[b];
30 
31             int k = 0;
32             for(int i=0; i<n; i++){
33                 if(i==0 || p[i].x!=p[i-1].x){
34                     k++;
35                     on[k] = on2[k] = 0;
36                     if(k==0) zl[k] = 0;
37                     else zl[k] = zl[k-1] + on2[k-1] - on[k-1];
38                 }
39                 if(p[i].y>ymin && p[i].y<ymax) on[k]++;
40                 if(p[i].y>=ymin && p[i].y<=ymax) on2[k]++;
41             }
42             if(k<=2) return n;
43 
44             int M = 0;
45             for(int j=1; j<=k; j++){
46                 ans = max(ans, zl[j]+on2[j]+M);
47                 M = max(M, on[j]-zl[j]);
48             }
49         }
50     }
51     return ans;
52 }
53 int main(){
54 #ifndef DEBUG
55     freopen("in.txt", "r", stdin);
56 #endif
57     int cas=0;
58     while(scanf("%d", &n)==1 && n){
59         for(int i=0; i<n; i++){
60             scanf("%d%d", &p[i].x, &p[i].y);
61             y[i]=p[i].y;
62         }
63         printf("Case %d: %d\n", ++cas, solve());
64     }
65     return 0;
66 }

这题感觉自己还是没理解透彻。

目录
相关文章
|
7月前
|
网络安全 开发工具 数据安全/隐私保护
ipa 如何安装到 iphone
ipa 如何安装到 iphone
|
传感器 编解码 算法
拿到iPhone X 后,你首先要做的10件事!
据 iPhone X 全球正式发售也近两周了,国内外媒体对这款代表着苹果未来10年发展方向的新机,已有了不少评测和总结,科技君今天就给各位果粉小伙伴们整理下有关 iPhone X 上手的十个必备技巧,助你发挥出它全部的潜力和乐趣。
208 0
拿到iPhone X 后,你首先要做的10件事!
|
编解码 物联网 5G
Galaxy Fold2再爆料,除了高刷还会降价
三星是最早宣布做折叠屏手机的厂商,但Galaxy Fold系列的诞生却一波三折,在被爆出铰链、屏幕出现严重问题后,三星经过很长时间的调整终于在去年下半年正式发售了这款手机,国行版本于2019年11月发布,售价15999元。
153 0
Galaxy Fold2再爆料,除了高刷还会降价
|
Shell iOS开发
Iphone攻与防-一
iphone-越狱机Hook APP 价值
1649 0
|
iOS开发 编解码
为新 iPhone X 添加启动图片
Xcode9 的 iPhone X 启动图片 iPhone X 启动图片大小: Portrait size : 1125px × 2436px Landscape size:2436px × 1125px 在 Xcode9 中位置: iPhone X 启动图片.
1056 0