Advertisement
Guest User

Untitled

a guest
Nov 25th, 2015
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. struct point {
  11. ll x, y;
  12. };
  13.  
  14. ll gcd(ll a, ll b) {
  15. return b == 0 ? a : gcd(b, a % b);
  16. }
  17.  
  18. ll gcd(ll a, ll b, ll c) {
  19. if (c == 0 && a == 0)
  20. return b;
  21. if (c == 0 && b == 0)
  22. return a;
  23. return gcd(gcd(a, b), c);
  24. }
  25.  
  26. istream & operator>>(istream & in, point & p) {
  27. in >> p.x >> p.y;
  28. return in;
  29. }
  30.  
  31. bool operator<(point a, point b){
  32. return a.x < b.x || a.x == b.x && a.y < b.y;
  33. }
  34.  
  35. struct line {
  36. ll a, b, c;
  37. line(point p1, point p2) {
  38. a = p2.y - p1.y;
  39. b = p1.x - p2.x;
  40. c = -a * p1.x - b * p1.y;
  41. ll g = gcd(a, b, c);
  42. a /= g;
  43. b /= g;
  44. c /= g;
  45. if (a < 0 || a == 0 && b < 0 || a == 0 && b == 0 && c < 0) {
  46. a = -a;
  47. b = -b;
  48. c = -c;
  49. }
  50. }
  51. };
  52.  
  53. bool cmp(pair<point, point> a, pair<point, point> b) {
  54. return a.first < b.first;
  55. }
  56.  
  57. bool operator<(line a, line b) {
  58. return a.a < b.a || a.a == b.a && a.b < b.b || a.a == b.a && a.b == b.b && a.c < b.c;
  59. }
  60.  
  61. map <line, vector<pair <point, point> > > mp;
  62.  
  63. int main()
  64. {
  65. point a, b;
  66. ll n, res = 0;
  67. cin >> n;
  68. for (int i = 0; i < n; i++) {
  69. cin >> a >> b;
  70. if (b < a)
  71. swap(a, b);
  72. mp[line(a, b)].push_back(make_pair(a, b));
  73. }
  74. for (map <line, vector<pair <point, point> > >::iterator cur = mp.begin(); cur != mp.end(); cur++) {
  75. sort((*cur).second.begin(), (*cur).second.end(), cmp);
  76. for (int i = 0; i < (*cur).second.size(); i++) {
  77. int l = i, r = (int) (*cur).second.size();
  78. while (r - l > 1) {
  79. int m = (l + r) / 2;
  80. if ((*cur).second[m].first < (*cur).second[i].second)
  81. l = m;
  82. else
  83. r = m;
  84. }
  85. res += l - i;
  86. //cout << (*cur).first.a << " " << (*cur).first.b << " " << (*cur).first.c << endl;
  87. }
  88. }
  89. cout << res;
  90. return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement