fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <list>
  6. #include <climits>
  7. #include <string>
  8. #include <stack>
  9. #include <map>
  10. #include <set>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstring>
  14. #include <cstdlib>
  15. #include <sstream>
  16. #include <iomanip>
  17.  
  18. #define ALL(v) v.begin(), v.end()
  19. #define REP(i, a, b) for(int i = a; i < b; i++)
  20. #define REPD(i, a, b) for(int i = a; i > b; i--)
  21. #define REPLL(i, a, b) for(ll i = a; i < b; i++)
  22. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  23. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  24. #define FORLL(i, a, b) for(ll i = a; i <= b; i++)
  25. #define INF 100001
  26.  
  27. #define vit vector<int>::iterator
  28. #define sit set<int>::iterator
  29. #define vi vector<int>
  30. #define vpii vector<pii >
  31.  
  32. #define ll long long
  33. #define ld long double
  34.  
  35. #define PB push_back
  36. #define MP make_pair
  37. #define pii pair<int, int>
  38. #define pld pair<ld, ld>
  39. #define st first
  40. #define nd second
  41.  
  42. #define EPS 1e-9
  43. #define PI acos(-1.0)
  44. #define MAXN 1000
  45.  
  46. using namespace std;
  47.  
  48. int z, n, a, b;
  49.  
  50. struct point {
  51.     ld x, y;
  52.     point() { x = y = 0.0; }
  53.     point(ld _x, ld _y) : x(_x), y(_y) {}
  54. };
  55.  
  56. struct vec {
  57.     ld x, y;
  58.     vec(ld _x, ld _y) : x(_x), y(_y) {}
  59. };
  60.  
  61. ld cross(vec a, vec b) {
  62.     return a.x * b.y - a.y * b.x;
  63. }
  64.  
  65. vec make_vec(point a, point b) {       // convert 2 points to vector a->b
  66.     return vec(b.x - a.x, b.y - a.y);
  67. }
  68.  
  69. vec scale(vec v, ld s) {        // nonnegative s = [<1 .. 1 .. >1]
  70.     return vec(v.x * s, v.y * s);
  71. }
  72.  
  73. point translate(point p, vec v) {        // translate p according to v
  74.     return point(p.x + v.x , p.y + v.y);
  75. }
  76.  
  77. ld dot(vec a, vec b) {
  78.     return (a.x * b.x + a.y * b.y);
  79. }
  80.  
  81. ld norm_sq(vec v) {
  82.     return v.x * v.x + v.y * v.y;
  83. }
  84.  
  85.  
  86. ld ccw(point p, point q, point r) {
  87.     return cross(make_vec(p, q), make_vec(p, r)); // >=0 for collinear
  88. }
  89.  
  90. ld dist(point p1, point p2) {
  91.     return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
  92. }
  93.  
  94. struct line {
  95.     point a, b;
  96.     line() {}
  97.     line(point _a, point _b) : a(_a), b(_b) {
  98.         if(a.x > b.x) swap(a, b);
  99.     }
  100.  
  101.     line get_perpendicular() const {
  102.         return line(point((-1.0)*a.y,a.x),point((-1.0)*b.y,b.x));
  103.     }
  104.  
  105.     point get_point() const {
  106.         vec v = make_vec(a, point(0, 0));
  107.         return translate(b, v);
  108.     }
  109.  
  110.     bool operator<(const line& l) const {
  111.         return ccw(point(0, 0), get_point(), l.get_point()) > EPS;
  112.     }
  113.  
  114.     bool operator==(const line& l) const {
  115.         return fabs(ccw(point(0, 0), get_point(), l.get_point())) < EPS ;
  116.     }
  117. };
  118.  
  119. ld cross(line a, line b)  {
  120.     return cross(make_vec(a.a, a.b), make_vec(b.a, b.b));
  121. }
  122.  
  123.  
  124. map<pair<line, ld>, ll> m;
  125. vector<line> lines;
  126.  
  127. ld dist_to_line(point p, point a, point b, point &c) {
  128.   // formula: c = a + u * ab
  129.     vec ap = make_vec(a, p), ab = make_vec(a, b);
  130.     ld u = dot(ap, ab) / norm_sq(ab);
  131.     c = translate(a, scale(ab, u));                  // translate a to c
  132.     return dist(p, c);
  133. }
  134.  
  135. ld get_dist(int i, int j) {
  136.     point c;
  137.     return dist_to_line(lines[i].a, lines[j].a, lines[j].b, c);
  138. }
  139.  
  140.  
  141. int main()
  142. {
  143.     ios_base::sync_with_stdio(0);
  144.     cin >> z;
  145.  
  146.     while(z--) {
  147.         m.clear();
  148.         cin >> n;
  149.         lines.clear();
  150.         REP(i, 0, n) {
  151.             cin >> a >> b;
  152.             point p1(a, b);
  153.  
  154.             cin >> a >> b;
  155.             point p2(a, b);
  156.  
  157.             line l = line(p1, p2);
  158.             lines.PB(l);
  159.         }
  160.         REP(i, 0, lines.size()) REP(j, i+1, lines.size()) {
  161.             if(lines[i] == lines[j]) {
  162.                 m[make_pair(lines[i], get_dist(i, j))]++;
  163.             }
  164.         }
  165.         ll result = 0;
  166.         for(map<pair<line, ld>, ll>::iterator it = m.begin(); it != m.end() ; it++) {
  167.             result += it->nd * m[MP(it->st.st.get_perpendicular(), it->st.nd)];
  168.         }
  169.         cout << result/2 << endl;
  170.     }
  171.     return 0;
  172. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2ZhOzJ
language:
C++14 (gcc 8.3)
created:
9 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!