Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2014
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.28 KB | None | 0 0
  1. // LDVSOFT team
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <cmath>
  8. #include <cassert>
  9. #include <string>
  10. #include <vector>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <stack>
  15. #include <deque>
  16. #include <bitset>
  17. #include <functional>
  18. #include <unordered_set>
  19. #include <unordered_map>
  20. #include <algorithm>
  21.  
  22. #define NAME "DEBUG"
  23.  
  24. using namespace std;
  25.  
  26. //#undef DEBUG
  27.  
  28. #ifdef HOME
  29.     #define DEBUG_INTER
  30. #endif
  31.  
  32. #ifdef DEBUG_INTER
  33.     #define iprintf(...) printf("OUT:" __VA_ARGS__ ), fflush(stdout)
  34. #else
  35.     #define iprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
  36. #endif
  37.  
  38. #ifdef DEBUG
  39.     #define eprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
  40. #else
  41.     #define eprintf(...)
  42. #endif
  43.  
  44. #ifdef WIN32
  45.     #define LLC "%I64d"
  46.     #define ULLC "%I64u"
  47. #else
  48.     #ifdef WIN64
  49.         #define LLC "%I64d"
  50.         #define ULLC "%I64u"
  51.     #else
  52.         #define LLC "%lld"
  53.         #define ULLC "%llu"
  54.     #endif
  55. #endif
  56.  
  57. #define pb push_back
  58. #define mp make_pair
  59. #define scn second
  60. #define frs first
  61. #define ins insert
  62.  
  63. template <typename A>
  64. using setit = typename set<A>::iterator;
  65. template <typename A, typename B>
  66. using mapit = typename map<A, B>::iterator;
  67.  
  68. using uchar = unsigned char;
  69. using uint  = unsigned int;
  70. using ll    =          long long;
  71. using ull   = unsigned long long;
  72. using ld    =          long double;
  73.  
  74. using pii = pair<int, int>;
  75.  
  76. int const N(2000);
  77. int const M(N * N);
  78. ld const EPS(1e-5);
  79.  
  80. struct Vector
  81. {
  82.     int x, y;
  83.     explicit Vector(int x = 0, int y = 0):
  84.         x(x),
  85.         y(y)
  86.     {
  87.     }
  88.  
  89.     Vector operator +(Vector const b) const
  90.     {
  91.         return Vector(x + b.x, y + b.y);
  92.     }
  93.     Vector operator -(Vector const b) const
  94.     {
  95.         return Vector(x - b.x, y - b.y);
  96.     }
  97.     Vector operator *(int const k) const
  98.     {
  99.         return Vector(x * k, y * k);
  100.     }
  101.     int operator *(Vector const b) const
  102.     {
  103.         return x * b.x + y * b.y;
  104.     }
  105.     int operator %(Vector const b) const
  106.     {
  107.         return x * b.y - y * b.x;
  108.     }
  109.     ld len()
  110.     {
  111.         return sqrt(x * x + y * y);
  112.     }
  113. };
  114.  
  115. struct Line
  116. {
  117.     Vector u, v;
  118.    
  119.     Line(Vector a = Vector(0, 0), Vector b = Vector(0, 0)):
  120.         u(a),
  121.         v(a - b)
  122.     {
  123.         if (v.y < 0 || (v.y == 0 && v.x < 0))
  124.             v = v * -1;
  125.     }
  126.  
  127.     bool operator <(Line const &l) const
  128.     {
  129.         return this->v % l.v > 0;
  130.     }
  131.  
  132.     bool operator ==(Line const &l) const
  133.     {
  134.         return this->v % l.v == 0;
  135.     }
  136. };
  137.  
  138. ld distance(Line a, Line b)
  139. {
  140.     return abs((b.u - a.u) % (b.u + b.v - a.u)) / b.v.len();
  141. }
  142.  
  143. int n;
  144. Line lines[N];
  145. int cnt1, cnt2;
  146. ld dist1[M], dist2[M];
  147.  
  148. int main(void)
  149. {
  150.     #ifdef HOME
  151.     {        
  152.         assert(freopen(NAME".in", "r", stdin));
  153.         assert(freopen(NAME".out", "w", stdout));
  154.     }
  155.     #endif
  156.  
  157.     scanf("%d", &n);   
  158.     for (int i(0); i < n; ++i)
  159.     {
  160.         int x1, x2, y1, y2;
  161.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  162.         lines[i] = Line(Vector(x1, y1), Vector(x2, y2));
  163.     }
  164.  
  165.     sort(lines, lines + n);
  166.  
  167.     #ifdef DEBUG
  168.     {
  169.         for (int i(0); i < n; ++i)
  170.             printf("! %d | u = %d %d v = %d %d\n", i, lines[i].u.x, lines[i].u.y, lines[i].v.x, lines[i].v.y);
  171.     }
  172.     #endif
  173.  
  174.     int l1, r1, l2, r2;
  175.     ll ans(0);
  176.     for (l2 = 0; l2 < n; ++l2)
  177.     {
  178.         if (lines[l2].v.x <= 0)
  179.             break;
  180.     }
  181.     for (l1 = 0; l1 < n; l1 = r1)
  182.     {
  183.         if (lines[l1].v.x <= 0)
  184.             break;
  185.         r1 = l1;
  186.         while (r1 < n && lines[r1] == lines[l1])
  187.             ++r1;
  188.        
  189.         while (l2 < n && lines[l2].v * lines[l1].v > 0)
  190.             ++l2;
  191.         if (l2 == n)
  192.             break;
  193.         r2 = l2;
  194.         while (r2 < n && lines[r2] == lines[l2])
  195.             ++r2;
  196.  
  197.         eprintf("! %d %d   %d %d\n", l1, r1, l2, r2);
  198.  
  199.         cnt1 = 0;
  200.         cnt2 = 0;
  201.         for (int i(l1); i != r1; ++i)
  202.             for (int j(i + 1); j != r1; ++j)
  203.             {
  204.                 ld d(distance(lines[i], lines[j]));
  205.                 if (d > EPS)
  206.                 {
  207.                     eprintf("!   d1 = %.9lf\n", double(d));
  208.                     dist1[cnt1++] = d; 
  209.                 }  
  210.             }    
  211.         for (int i(l2); i != r2; ++i)
  212.             for (int j(i + 1); j != r2; ++j)
  213.             {
  214.                 ld d(distance(lines[i], lines[j]));
  215.                 if (d > EPS)
  216.                 {
  217.                     eprintf("!   d2 = %.9lf\n", double(d));
  218.                     dist2[cnt2++] = d; 
  219.                 }  
  220.             }    
  221.  
  222.         sort(dist1, dist1 + cnt1);
  223.         sort(dist2, dist2 + cnt2);
  224.  
  225.         int ll1(0), rr1(0), ll2(0), rr2(0);
  226.         for (; ll1 < cnt1; ll1 = rr1)
  227.         {
  228.             rr1 = ll1;
  229.             while (rr1 < cnt1 && dist1[rr1] - dist1[ll1] < EPS)
  230.                 ++rr1;
  231.             while (ll2 < cnt2 && dist2[ll2] + EPS < dist1[ll1])
  232.                 ++ll2;
  233.             if (ll2 == cnt2)
  234.                 break;
  235.             if (dist2[ll2] > dist1[ll1] + EPS)
  236.             rr2 = ll2;
  237.             while (rr2 < cnt2 && dist2[rr2] - dist2[ll2] < EPS)
  238.                 ++rr2;                         
  239.             eprintf("!   %d %d   %d %d\n", ll1, rr1, ll2, rr2);
  240.             ans += ll(rr1 - ll1) * ll(rr2 - ll2);
  241.         }
  242.     }
  243.     printf(LLC "\n", ans);
  244.  
  245.     return 0;
  246. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement