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
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; typedef pair<int,int> P; int (){ 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); } void solve(){ 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("%dn",ans); } int main(){ init(); solve(); return 0; }
|
近期评论