C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2019-06-29 13:26:57

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<algorithm>
using namespace std;
int n,m,ans,x[110],y[110],b[110],bt,t[4],te,c[110],ct,X,Y;
int main(){
	scanf("%d%d",&n,&m);
	ans=n;
	fo(i,1,n) scanf("%d%d",&x[i],&y[i]);
	fo(i,1,n) b[i]=x[i];
	bt=n;
	sort(b+1,b+bt+1);
	bt=unique(b+1,b+bt+1)-b-1;
	fo(i,1,n) c[i]=y[i];
	ct=n;
	sort(c+1,c+ct+1);
	ct=unique(c+1,c+ct+1)-c-1;
	fo(i,2,bt)
		fo(j,2,ct){
			X=(b[i-1]+b[i])/2;
			Y=(c[j-1]+c[j])/2;
			fo(k,0,3) t[k]=0;
			fo(k,1,n){
				te=0;
				if (x[k]>X) te++;
				if (y[k]>Y) te+=2;
				t[te]++;
			}
			te=t[0];
			fo(k,1,3) if (t[k]>te) te=t[k];
			if (te<ans) ans=te;
		}
	printf("%d\n",ans);
	return 0;
}

Python3(3.9) 解法, 执行用时: 1275ms, 内存消耗: 3016K, 提交时间: 2020-12-19 23:12:13

a = input()
N, B = [int(x) for x in a.split()]
xys = []
for _ in range(N):
    x, y = [int(z) for z in input().split()]
    xys.append((x, y))

xsplits = set()
ysplits = set()
minmax = N
for (x, y) in xys:
    xsplits.add(x+1)
    xsplits.add(x-1)
    ysplits.add(y+1)
    ysplits.add(y-1)
for xm in xsplits:
    for ym in ysplits:
        count1 = sum([x < xm and y < ym for (x, y) in xys])
        count2 = sum([x < xm and y > ym for (x, y) in xys])
        count3 = sum([x > xm and y < ym for (x, y) in xys])
        count4 = sum([x > xm and y > ym for (x, y) in xys])
        maxcount = max(count1, count2, count3, count4)
        minmax = min(minmax, maxcount)
    
print(minmax)
        
        

C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 472K, 提交时间: 2019-06-30 19:07:09

#include<bits/stdc++.h>
using namespace std;
int x[110],y[110];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>x[i]>>y[i];
	int ans=2e9;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		int a=0,b=0,c=0,d=0;
		for(int k=1;k<=n;k++)
		if(x[k]<=x[i]&&y[k]<=y[j])a++;
		else if(x[k]<=x[i]&&y[k]>y[j])b++;
		else if(x[k]>x[i]&&y[k]<=y[j])c++;
		else d++;
		ans=min(ans,max(max(a,b),max(c,d)));
	}
	cout<<ans<<"\n";
	return 0;
}