Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LDVSOFT team
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <cassert>
- #include <string>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <bitset>
- #include <functional>
- #include <unordered_set>
- #include <unordered_map>
- #include <algorithm>
- #define NAME "DEBUG"
- using namespace std;
- //#undef DEBUG
- #ifdef HOME
- #define DEBUG_INTER
- #endif
- #ifdef DEBUG_INTER
- #define iprintf(...) printf("OUT:" __VA_ARGS__ ), fflush(stdout)
- #else
- #define iprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
- #endif
- #ifdef DEBUG
- #define eprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
- #else
- #define eprintf(...)
- #endif
- #ifdef WIN32
- #define LLC "%I64d"
- #define ULLC "%I64u"
- #else
- #ifdef WIN64
- #define LLC "%I64d"
- #define ULLC "%I64u"
- #else
- #define LLC "%lld"
- #define ULLC "%llu"
- #endif
- #endif
- #define pb push_back
- #define mp make_pair
- #define scn second
- #define frs first
- #define ins insert
- template <typename A>
- using setit = typename set<A>::iterator;
- template <typename A, typename B>
- using mapit = typename map<A, B>::iterator;
- using uchar = unsigned char;
- using uint = unsigned int;
- using ll = long long;
- using ull = unsigned long long;
- using ld = long double;
- using pii = pair<int, int>;
- int const N(2000);
- int const M(N * N);
- ld const EPS(1e-5);
- struct Vector
- {
- int x, y;
- explicit Vector(int x = 0, int y = 0):
- x(x),
- y(y)
- {
- }
- Vector operator +(Vector const b) const
- {
- return Vector(x + b.x, y + b.y);
- }
- Vector operator -(Vector const b) const
- {
- return Vector(x - b.x, y - b.y);
- }
- Vector operator *(int const k) const
- {
- return Vector(x * k, y * k);
- }
- int operator *(Vector const b) const
- {
- return x * b.x + y * b.y;
- }
- int operator %(Vector const b) const
- {
- return x * b.y - y * b.x;
- }
- ld len()
- {
- return sqrt(x * x + y * y);
- }
- };
- struct Line
- {
- Vector u, v;
- Line(Vector a = Vector(0, 0), Vector b = Vector(0, 0)):
- u(a),
- v(a - b)
- {
- if (v.y < 0 || (v.y == 0 && v.x < 0))
- v = v * -1;
- }
- bool operator <(Line const &l) const
- {
- return this->v % l.v > 0;
- }
- bool operator ==(Line const &l) const
- {
- return this->v % l.v == 0;
- }
- };
- ld distance(Line a, Line b)
- {
- return abs((b.u - a.u) % (b.u + b.v - a.u)) / b.v.len();
- }
- int n;
- Line lines[N];
- int cnt1, cnt2;
- ld dist1[M], dist2[M];
- int main(void)
- {
- #ifdef HOME
- {
- assert(freopen(NAME".in", "r", stdin));
- assert(freopen(NAME".out", "w", stdout));
- }
- #endif
- scanf("%d", &n);
- for (int i(0); i < n; ++i)
- {
- int x1, x2, y1, y2;
- scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
- lines[i] = Line(Vector(x1, y1), Vector(x2, y2));
- }
- sort(lines, lines + n);
- #ifdef DEBUG
- {
- for (int i(0); i < n; ++i)
- 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);
- }
- #endif
- int l1, r1, l2, r2;
- ll ans(0);
- for (l2 = 0; l2 < n; ++l2)
- {
- if (lines[l2].v.x <= 0)
- break;
- }
- for (l1 = 0; l1 < n; l1 = r1)
- {
- if (lines[l1].v.x <= 0)
- break;
- r1 = l1;
- while (r1 < n && lines[r1] == lines[l1])
- ++r1;
- while (l2 < n && lines[l2].v * lines[l1].v > 0)
- ++l2;
- if (l2 == n)
- break;
- r2 = l2;
- while (r2 < n && lines[r2] == lines[l2])
- ++r2;
- eprintf("! %d %d %d %d\n", l1, r1, l2, r2);
- cnt1 = 0;
- cnt2 = 0;
- for (int i(l1); i != r1; ++i)
- for (int j(i + 1); j != r1; ++j)
- {
- ld d(distance(lines[i], lines[j]));
- if (d > EPS)
- {
- eprintf("! d1 = %.9lf\n", double(d));
- dist1[cnt1++] = d;
- }
- }
- for (int i(l2); i != r2; ++i)
- for (int j(i + 1); j != r2; ++j)
- {
- ld d(distance(lines[i], lines[j]));
- if (d > EPS)
- {
- eprintf("! d2 = %.9lf\n", double(d));
- dist2[cnt2++] = d;
- }
- }
- sort(dist1, dist1 + cnt1);
- sort(dist2, dist2 + cnt2);
- int ll1(0), rr1(0), ll2(0), rr2(0);
- for (; ll1 < cnt1; ll1 = rr1)
- {
- rr1 = ll1;
- while (rr1 < cnt1 && dist1[rr1] - dist1[ll1] < EPS)
- ++rr1;
- while (ll2 < cnt2 && dist2[ll2] + EPS < dist1[ll1])
- ++ll2;
- if (ll2 == cnt2)
- break;
- if (dist2[ll2] > dist1[ll1] + EPS)
- rr2 = ll2;
- while (rr2 < cnt2 && dist2[rr2] - dist2[ll2] < EPS)
- ++rr2;
- eprintf("! %d %d %d %d\n", ll1, rr1, ll2, rr2);
- ans += ll(rr1 - ll1) * ll(rr2 - ll2);
- }
- }
- printf(LLC "\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement