fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<set>
  4. #include<map>
  5. using namespace std;
  6. pair<int,int> dat[100000];
  7. int x[100000];
  8. int y[100000];
  9. int h,w,n;
  10. int L=-2100000000;
  11. int R=2100000000;
  12. int X[100001],Y[100001];
  13. long long calc(){
  14. 	set<int> S;
  15. 	map<int,int>M;
  16. 	for(int i=0;i<n;i++)M[dat[i].second]++;
  17. 	S.insert(L);S.insert(R);
  18. 	std::sort(x,x+n);
  19. 	std::sort(y,y+n);
  20. 	int xx=0;
  21. 	int yy=0;
  22. 	X[xx++]=x[0];
  23. 	Y[yy++]=y[0];
  24. 	for(int i=1;i<n;i++){
  25. 		if(x[i]!=x[i-1])X[xx++]=x[i];
  26. 		if(y[i]!=y[i-1])Y[yy++]=y[i];
  27. 	}
  28. 	X[xx++]=R;
  29. 	Y[yy++]=R;
  30. 	std::sort(dat,dat+n);
  31. 	long long ret=0;
  32. 	int at=0;
  33. 	for(int i=0;i<n;i++){
  34. 		if(i<n-1&&dat[i].first==dat[i+1].first)continue;
  35. 		long long left=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,L)))).second;
  36. 		long long right=(*(lower_bound(dat,dat+n,make_pair(dat[i].first,R))-1)).second;
  37. 		int A=lower_bound(Y,Y+yy,left-1)-Y;
  38. 		int B=yy-(upper_bound(Y,Y+yy,right+1)-Y)-1;
  39. 		ret=max(ret,max(left-2-A,w-right-2-B));
  40. 		left=*(--(S.lower_bound(left)));
  41. 		right=*(S.upper_bound(right));
  42. 		A=lower_bound(Y,Y+yy,left)-Y;
  43. 		B=yy-(upper_bound(Y,Y+yy,right)-Y)-1;
  44. 		int C=xx-(upper_bound(X,X+xx,dat[i].first)-X)-1;
  45. 		ret=max(ret,max(left+h-dat[i].first-1-A-C,w-right+h-dat[i].first-2-B-C));
  46. 		while(at<n&&dat[at].first==dat[i].first){
  47. 			M[dat[at].second]--;
  48. 			if(M[dat[at].second]==0)S.insert(dat[at].second);
  49. 			at++;
  50. 		}
  51. 	}
  52. 	return ret;
  53. }
  54. int main(){
  55. 	scanf("%d%d%d",&h,&w,&n);
  56. 	for(int i=0;i<n;i++){
  57. 		scanf("%d%d",x+i,y+i);
  58. 		dat[i]=make_pair(x[i],y[i]);
  59. 	}
  60. 	std::sort(x,x+n);
  61. 	std::sort(y,y+n);
  62. 	int H=h-1;
  63. 	int W=w-1;
  64. 	for(int i=1;i<n;i++){
  65. 		if(x[i]!=x[i-1])H--;
  66. 		if(y[i]!=y[i-1])W--;
  67. 	}
  68. 	long long A=(long long)H*W;
  69. 	long long B=0;
  70. 	for(int i=0;i<4;i++){
  71. 		long long C=calc();
  72. 	//	printf("%d\n",C);
  73. 		B=max(B,C);
  74. 		for(int j=0;j<n;j++){
  75. 			x[j]=w-dat[j].second+1;y[j]=dat[j].first;
  76. 			dat[j]=make_pair(x[j],y[j]);
  77. 		}
  78. 		swap(h,w);
  79. 	}
  80. 	printf("%lld\n",A+B);
  81. }
Success #stdin #stdout 0s 5784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/LyEW2H
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!