fork(2) download
copy 
  1. //by Vanjape Rajas Mangesh
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long int	LL;
  8. typedef pair<LL ,LL >   II;
  9. typedef vector< II >      VII;
  10. typedef vector<int>     VI;
  11. typedef vector< VI > 	VVI;
  12.  
  13. #define PB push_back
  14. #define MP make_pair
  15. #define F first
  16. #define S second
  17. #define SZ(a) (int)(a.size())
  18. #define ALL(a) a.begin(),a.end()
  19. #define SET(a,b) memset(a,b,sizeof(a))
  20.  
  21. #define si(n) scanf("%d",&n)
  22. #define dout(n) printf("%d\n",n)
  23. #define sll(n) scanf("%lld",&n)
  24. #define lldout(n) printf("%lld\n",n)
  25. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  26.  
  27. #define TRACE
  28.  
  29. #ifdef TRACE
  30. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  31. template <typename Arg1>
  32. void __f(const char* name, Arg1&& arg1){
  33. 	cerr << name << " : " << arg1 << std::endl;
  34. }
  35. template <typename Arg1, typename... Args>
  36. void __f(const char* names, Arg1&& arg1, Args&&... args){
  37. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  38. }
  39. #else
  40. #define trace(...)
  41. #endif
  42.  
  43. //FILE *fin = freopen("in","r",stdin);
  44. //FILE *fout = freopen("out","w",stdout);
  45.  
  46. LL x[4],y[4],arr0[3],arr1[3];
  47. II func(LL a,LL b)
  48. {
  49. 	LL xx=1,yy=1;
  50. 	if(a<0)
  51. 		xx=-1;
  52. 	if(b<0)
  53. 		yy=-1;
  54. 	return MP(xx*(max(abs(a)-1,0LL)/x[1]+(a<0)),yy*(max(abs(b)-1,0LL)/y[1]+(b<0)));
  55. }
  56. LL getarea(LL x1,LL y1,LL x2,LL y2)
  57. {
  58. 	LL a=max(0LL,min(x2,x[3])-max(x1,x[2]));
  59. 	LL b=max(0LL,min(y2,y[3])-max(y1,y[2]));
  60. //	trace(x1,y1,x2,y2,a*b);
  61. 	return a*b;
  62. }
  63. int main()
  64. {
  65. 	LL t;
  66. 	cin>>t;
  67. 	while(t--)
  68. 	{		
  69. 		LL k;
  70. 		for(LL i=0;i<4;i++)
  71. 		{
  72. 			cin>>x[i]>>y[i];
  73. 		}
  74. 		x[3]+=x[2],y[3]+=y[2];
  75. 		x[1]+=x[0],y[1]+=y[0];
  76. 		for(LL i=3;i>=0;i--)
  77. 		{
  78. 			x[i]-=x[0],y[i]-=y[0];
  79. 		}
  80. 		cin>>k;
  81. 		arr0[0]=-x[1],arr0[1]=0,arr0[2]=x[1];
  82. 		arr1[0]=-y[1],arr1[1]=0,arr1[2]=y[1];
  83. 		LL mx=0;
  84. 		for(LL l=2;l<4;l++)
  85. 			for(LL m=2;m<4;m++)
  86. 				for(LL i=0;i<3;i++)
  87. 					for(LL j=0;j<3;j++)
  88. 					{
  89. 						II tmp=func(x[l]+arr0[i],y[m]+arr1[j]);
  90. 						LL temp=getarea(tmp.F*x[1],tmp.S*y[1],(tmp.F+1)*x[1],(tmp.S+1)*y[1]);
  91. 						if(mx<temp && abs(tmp.F)+abs(tmp.S)<=k)
  92. 							mx=temp;
  93. 					}
  94. 		for(LL i=0;i<3;i++)
  95. 			for(LL j=0;j<3;j++)
  96. 			{
  97. 				LL temp=getarea(arr0[i],arr1[j],arr0[i]+x[1],arr1[j]+y[1]);
  98. 				II tmp;
  99. 				tmp.F=arr0[i]/x[1];
  100. 				tmp.S=arr1[j]/y[1];
  101. 				if(mx<temp && abs(tmp.F)+abs(tmp.S)<=k)
  102. 						mx=temp;
  103. 			}
  104. //		cout<<mx<<"\n";
  105. 		if(x[2]<0&&0<x[3])
  106. 		{
  107. 			x[2]=0;
  108. 		}
  109. 		if(y[2]<0&&0<y[3])
  110. 		{
  111. 			y[2]=0;
  112. 		}
  113. 		for(LL l=2;l<4;l++)
  114. 			for(LL m=2;m<4;m++)
  115. 				for(LL i=0;i<3;i++)
  116. 					for(LL j=0;j<3;j++)
  117. 					{
  118. 						II tmp=func(x[l]+arr0[i],y[m]+arr1[j]);
  119. 						LL temp=getarea(tmp.F*x[1],tmp.S*y[1],(tmp.F+1)*x[1],(tmp.S+1)*y[1]);
  120. 						if(mx<temp && abs(tmp.F)+abs(tmp.S)<=k)
  121. 							mx=temp;
  122. 					}
  123. 		cout<<mx<<"\n";
  124.  
  125. 	}
  126. 	return 0;
  127. }
Runtime error #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u97AYD
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!