题解
模拟即可。
拿线扫描，然后直接模拟。
可以二分，套上线段树可以做到$O(nlogn)$的复杂度。
实际上应该不需要离散化。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
P pp[1005],p1[1005],p2[1005];
int n;
int cmp(P a,P b){
return a.second<b.second||(a.second==b.second&&a.first<b.first);
}
void init(){
n=read();
for(int i=1;i<=n;i++)pp[i].first=read(),pp[i].second=read();
sort(pp+1,pp+n+1);
int cnt=1;
for(int i=2;i<=n;i++){
if(pp[i-1].first==pp[i].first)
pp[i-1].first=cnt;
else pp[i-1].first=cnt,cnt+=2;
}
pp[n].first=cnt;
memcpy(p1+1,pp+1,sizeof(P)*n);
sort(pp+1,pp+n+1,cmp);
cnt=1;
for(int i=2;i<=n;i++){
if(pp[i-1].second==pp[i].second)
pp[i-1].second=cnt;
else pp[i-1].second=cnt,cnt+=2;
}
pp[n].second=cnt;
memcpy(p2+1,pp+1,sizeof(P)*n);
//离散化之后分别按照x,y坐标排序，进行扫描。。。
}
void solve(){
//a | c
//-------
//b | d
//一开始放在最左点左边，最下点下面
int a=0,b=0,c=0,d=0,A=0,B=n,sep,ans=n,maxi;
p1[0].first=0,p2[0].second=0;
for(int i=1;i<=n;i++,A++,B--){
if(p1[i].first==p1[i-1].first)continue;
a=A,c=B,b=d=0;
sep=p1[i].first-1;
for(int j=1;j<=n;j++){
if(p2[j].second!=p2[j-1].second){
maxi=0;
if(maxi<a)maxi=a;if(maxi<b)maxi=b;
if(maxi<c)maxi=c;if(maxi<d)maxi=d;
if(maxi<ans)ans=maxi;
}
if(p2[j].first<sep)
a--,b++;
else c--,d++;
}
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}