题目描述
给出平面上的n个点，请找出一个边与坐标轴平行的矩形，使得它的边界上有尽量多的点
输入输出格式
输入格式：
第一行一个整数n，为平面内点的个数。
第2~n+1行每行两个整数，为点的横、纵坐标。
输出格式：
只有一个数，为所取矩形边界上能包含尽量多的点的个数。
输入输出样例
输入样例#1：
10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6
输出样例#1：
7
说明
【数据范围】
对于40%的数据，n<=30
对于100%的数据，n<=300，各点的横、纵坐标在1~100范围内
此题应该是一道略有思维难度的题，涉及到数学逻辑思维的运用，对矩形的构造需要一定的想象能力。
要点：
1、枚举两个点，把他们作为矩形上两个相对的顶点，构建矩形；
2、特判所有点在一条直线上的情况，此时输出点的个数；
3、在两个点外另找一个点，分作矩形边界点和矩形内部点两种情况，记下此时矩形边上点的个数、矩形内部点的个数、矩形内部加边上点的个数，最后比较出最大值即可。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
struct dd
{
int x,y;
}a[310];
int on[110],in[110],l[110],num[110],i,j,k,n,ans=0;
int main()
{
cin>>n;
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
int x1=1,y1=1;
for(i=2;i<=n;i++)//进行特判，若所有点在同一直线上，则输出点的个数
{
if(a[i].y!=a[1].y)
y1=0;
if(a[i].x!=a[1].x)
x1=0;
}
if(x1||y1)//所有点横坐标或纵坐标全相同的情况
{
cout<<n;
return 0;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i].y>=a[j].y)//保证a[i].y<a[j].y，将a[i]和a[j]两点作为矩形两个相对的顶点，构造矩形
continue;
else
{
memset(num,0,sizeof(num));//矩形边上点的个数
memset(on,0,sizeof(on));//矩形中间点的个数
memset(in,0,sizeof(in));//矩形中间加边上点的个数
for(k=1;k<=n;k++)
{
if(a[k].y==a[i].y||a[k].y==a[j].y)//若a[k]在矩形边上
{
num[a[k].x]++;
in[a[k].x]++;
}
if(a[k].y>a[i].y&&a[k].y<a[j].y)//a[k].y在a[i].y与a[j].y之间时
{
on[a[k].x]++;
in[a[k].x]++;
}
}
l[1]=0;
for(k=2;k<=100;k++)
l[k]=l[k-1]+num[k-1];//当a[k]作为边上点时矩形内点的个数
int max0=on[1]-l[1];
for(k=2;k<=100;k++)//当a[k]作为矩形中间点时矩形内点的个数
{
ans=max(in[k]+l[k]+max0,ans);
max0=max(max0,on[k]-l[k]);//矩形缩小
}
}
cout<<ans;
return 0;
}