fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <map>
  4. #include <cmath>
  5.  
  6. #define ll_int long long int
  7. #define l_double long double
  8. using namespace std;
  9.  
  10. class line_coeff {
  11. 	public:
  12.         ll_int a, b;
  13.         l_double c;
  14.  
  15. 		line_coeff(ll_int x, ll_int y, l_double z) {
  16. 			if(x < 0) {
  17. 				a = -x;
  18. 				b = -y;
  19. 				c = -z;
  20. 			}
  21. 			else {
  22. 				a = x;
  23. 				b = y;
  24. 				c = z;
  25. 			}
  26. 			minimize_coeff();
  27. 		}
  28.  
  29. 		friend ostream& operator << (ostream&, line_coeff);
  30.  
  31.         bool operator <(const line_coeff& rhs) const {
  32.             if(a==rhs.a && b==rhs.b && c==rhs.c) return false;
  33.             return true;
  34.         }
  35.  
  36.         bool operator >(const line_coeff& rhs) const {
  37.             if(a==rhs.a && b==rhs.b && c==rhs.c) return false;
  38.             return true;
  39.         }
  40.  
  41.         static ll_int gcd(ll_int x, ll_int y) {
  42. 			if(!y) return x;
  43. 			return gcd(y, x%y);
  44.         }
  45.  
  46.         void minimize_coeff() {
  47. 			ll_int gcd_val = gcd(abs(a), abs(b));
  48. 			a /= gcd_val;
  49. 			b /= gcd_val;
  50. 			c /= gcd_val;
  51.         }
  52. };
  53.  
  54. ostream& operator << (ostream &out, line_coeff coeff) {
  55. 	out<<coeff.a<<" "<<coeff.b<<" "<<coeff.c;
  56. 	return out;
  57. }
  58.  
  59. int main() {
  60. 	set<line_coeff> line_set;
  61.     ll_int t, n, a, b, ans, max_x, max_y, prev_val=0; l_double c;
  62.     map<pair<ll_int,ll_int>,ll_int> m;
  63.     cin>>t;
  64.     while(t--) {
  65. 		ans = 0;
  66. 		cin>>n;
  67. 		max_x = max_y = 0;
  68. 		while(n--) {
  69. 			ll_int prev_size = line_set.size();
  70. 			cin>>a>>b>>c;
  71. 			line_set.insert(line_coeff(a, b, c));
  72. 			if(a==0 && line_set.size()>prev_size) max_x++;
  73. 			if(b==0 && line_set.size()>prev_size) max_y++;
  74. 		}
  75. 		for(set<line_coeff>::iterator it=line_set.begin(); it!=line_set.end(); it++)
  76. 			m[make_pair(it->a,it->b)]++;
  77. 		ll_int max_val = 0;
  78. 		for(map<pair<ll_int,ll_int>,ll_int>::iterator it=m.begin(); it!=m.end(); it++) {
  79. 			if(it->second > max_val) max_val = it->second;
  80. 		}
  81. 		if(max_x>max_y && max_x>max_val) ans = max_x;
  82. 		else if(max_y>max_x && max_y>max_val) ans = max_y;
  83. 		else if(max_val==1 && n!=1) ans = 0;
  84. 		else ans = max_val;
  85. 		cout<<ans<<endl;
  86. 		line_set.clear();
  87.     }
  88.     return 0;
  89. }
  90.  
Time limit exceeded #stdin #stdout 5s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sfoJ0T
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!