fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<stdlib.h>
  5. #include<math.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<ll,ll>pii;
  9. typedef pair<pii,pii>pi4;
  10. typedef pair<pi4,pii>pi6;
  11. ll mod=1000000007;
  12. ll gcd(ll a,ll b)
  13. {
  14. 	for(;;)
  15. 	{
  16. 		if(a<b)
  17. 		{
  18. 			swap(a,b);
  19. 		}
  20. 		a%=b;
  21. 		if(a==0)
  22. 		{
  23. 			return b;
  24. 		}
  25. 	}
  26. }
  27. pii reduct(pii a)
  28. {
  29. 	if(a.second==0)
  30. 	{
  31. 		return make_pair(1LL,0LL);
  32. 	}
  33. 	if(a.first==0)
  34. 	{
  35. 		return make_pair(0LL,1LL);
  36. 	}
  37. 	ll g=gcd(abs(a.first),abs(a.second));
  38. 	if(a.second<0)
  39. 	{
  40. 		a.first=-a.first;
  41. 		a.second=-a.second;
  42. 	}
  43. 	return make_pair(a.first/g,a.second/g);
  44. }
  45. pii pls(pii a,pii b)
  46. {
  47. 	return reduct(make_pair(a.first*b.second+a.second*b.first,a.second*b.second));
  48. }
  49. pii mins(pii a,pii b)
  50. {
  51. 	return reduct(make_pair(a.first*b.second-a.second*b.first,a.second*b.second));
  52. }
  53. pii tim(pii a,pii b)
  54. {
  55. 	return reduct(make_pair(a.first*b.first,a.second*b.second));
  56. }
  57. pii div(pii a,pii b)
  58. {
  59. 	return reduct(make_pair(a.first*b.second,a.second*b.first));
  60. }
  61. pi4 getsum(pi4 a,pi4 b)
  62. {
  63. 	return make_pair(pls(a.first,b.first),pls(a.second,b.second));
  64. }
  65. pii getinc(pi4 a,pi4 b)
  66. {
  67. 	pii dx=mins(b.first,a.first);
  68. 	pii dy=mins(b.second,a.second);
  69. 	return div(dy,dx);
  70. }
  71. pi4 inv(ll za,ll zb,ll zc,ll zd)
  72. {
  73. 	pii dist=pls(tim(make_pair(za,zb),make_pair(za,zb)),tim(make_pair(zc,zd),make_pair(zc,zd)));
  74. 	return (make_pair(div(make_pair(za,zb),dist),div(make_pair(zc,zd),dist)));
  75. }
  76. vector<int>tov(vector<pii>vec)
  77. {
  78. 	pii now=make_pair(2000000000000000000LL,2000000000000000000LL);
  79. 	vector<int>ret;
  80. 	for(int i=0;i<vec.size();i++)
  81. 	{
  82. 		if(now!=vec[i])
  83. 		{
  84. 			ret.push_back(1);
  85. 			now=vec[i];
  86. 		}
  87. 		else
  88. 		{
  89. 			ret[ret.size()-1]++;
  90. 		}
  91. 	}
  92. 	return ret;
  93. }
  94. ll calc(vector<pii>v)
  95. {
  96. 	vector<int>vec=tov(v);
  97. 	ll ret=1;
  98. 	for(int i=0;i<vec.size();i++)
  99. 	{
  100. 		ret*=vec[i]+1;
  101. 		ret%=mod;
  102. 	}
  103. 	ret=(ret+mod-1-int(v.size()))%mod;
  104. 	return ret;
  105. }
  106. int main()
  107. {
  108. 	int num;
  109. 	scanf("%d",&num);
  110. 	vector<pi4>dat;
  111. 	for(int i=0;i<num;i++)
  112. 	{
  113. 		ll za,zb,zc,zd;
  114. 		scanf("%I64d%I64d%I64d%I64d",&za,&zb,&zc,&zd);
  115. 		dat.push_back(inv(za,zb,zc,zd));
  116. 	}
  117. 	vector<pi6>vec;
  118. 	for(int i=0;i<num;i++)
  119. 	{
  120. 		for(int j=i+1;j<num;j++)
  121. 		{
  122. 			vec.push_back(make_pair(getsum(dat[i],dat[j]),getinc(dat[i],dat[j])));
  123. 		}
  124. 	}
  125. 	sort(vec.begin(),vec.end());
  126. 	pi4 nowsum=make_pair(make_pair(2000000000000000000LL,2000000000000000000LL),make_pair(2000000000000000000LL,2000000000000000000LL));
  127. 	vector<pii>now;
  128. 	ll ret=0;
  129. 	for(int i=0;i<vec.size();i++)
  130. 	{
  131. 		if(nowsum!=vec[i].first)
  132. 		{
  133. 			if(!now.empty())
  134. 			{
  135. 				ret+=calc(now);
  136. 				ret%=mod;
  137. 			}
  138. 			now.clear();
  139. 			now.push_back(vec[i].second);
  140. 			nowsum=vec[i].first;
  141. 		}
  142. 		else
  143. 		{
  144. 			now.push_back(vec[i].second);
  145. 		}
  146. 	}
  147. 	ret+=calc(now);
  148. 	ret%=mod;
  149. 	printf("%I64d\n",ret);
  150. }
Success #stdin #stdout 0s 3320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
                                                               0
https://ideone.com/x3Xrqe
language:
C++ (gcc 8.3)
created:
10 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!