10.16T3 乱搞+最优性剪枝

这题实际上可以乱搞23333，然后就就AC了

我们先对x进行排序，然后用vector记录一下相同xy下点的个数

然后我们可以对这些同一行列点的个数排一个序，从大往小搜索

对于当前点的坐标我们可以用lower_bound二分确定左右的个数

在上下左右四个值里面取一个最小值

如果当前的行或列的点个数小于找到的最大值，直接剪掉就好了，然后。。。。就过了

复杂度O(n²logn)?神仙复杂度

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<map>
 5 #include<vector>
 6 #define N 100006
 7 using namespace std;
 8 struct node{
 9     long long x,y;
10 }e[N];
11 bool cmp(const node &a,const node &b){
12     if(a.x==b.x)return a.y<b.y;
13     return a.x<b.x;
14 }
15 struct T{
16     long long id,num;
17 }X[N],Y[N];
18 long long read(){
19     long long x=0,f=1;
20     char c=getchar();
21     while(!isdigit(c)){
22         if(c=='-')f=-1;
23         c=getchar();
24     }
25     while(isdigit(c)){
26         x=(x<<3)+(x<<1)+c-'0';
27         c=getchar();
28     }
29     return x*f;
30 }
31 bool bmp(const T&a,const T&b){
32     if(a.num==b.num)return a.id<b.id;
33     return a.num>b.num;
34 }
35 vector<long long>x[100001],y[100001];
36 map<long long,int>check;
37 int main(){
38 //    freopen("sern.in","r",stdin);
39 //    freopen("sern.out","w",stdout);
40     long long n;
41     cin>>n;
42     for(long long i=1;i<=n;i++){
43         e[i].x=read(),e[i].y=read();
44         check[e[i].x*1000000+e[i].y]=1;
45     }
46     sort(e+1,e+n+1,cmp);
47     for(long long i=1;i<=n;i++){
48         x[e[i].x].push_back(e[i].y),y[e[i].y].push_back(e[i].x);
49         check[e[i].x*1000000+e[i].y]=1;
50     }
51     for(long long i=1;i<=n;i++)X[i].num=x[i].size(),X[i].id=i;
52     for(long long i=1;i<=n;i++)Y[i].num=y[i].size(),Y[i].id=i;
53     sort(X+1,X+n+1,bmp);
54     sort(Y+1,Y+n+1,bmp);
55     long long max0=0;
56     long long num=0;
57     for(long long i=1;i<=n;i++){
58     //    cout<<i<<'
';
59         if((X[i].num)/2<max0)break;
60         long long min0=25000001;
61         for(long long j=1;j<=n;j++){
62             if((Y[j].num)/2<max0)break;
63             if(check[X[i].id*1000000+Y[j].id])continue;
64             long long x1=lower_bound(y[Y[j].id].begin(),y[Y[j].id].end(),X[i].id)-y[Y[j].id].begin();
65             long long y1=lower_bound(x[X[i].id].begin(),x[X[i].id].end(),Y[j].id)-x[X[i].id].begin();
66             long long sizx=x[X[i].id].size(),sizy=y[Y[j].id].size();
67             min0=min(x1,min(sizy-x1,min(y1,sizx-y1)));
68             if(min0>max0){
69                 max0=min0;
70                 num=1;
71             }    
72             else if(min0==max0){
73                 num++;
74             }        
75         }
76     }
77     cout<<max0<<'
'<<num;
78     return 0;
79 }

over