QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766810 | #7711. Rikka with Lines | crimson231 | AC ✓ | 810ms | 28696kb | C++23 | 6.3kb | 2024-11-20 18:42:35 | 2024-11-20 18:42:39 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <cstring>
#include <cassert>
//typedef long long _int128;
typedef __int128 _int128;
typedef long long ll;
typedef double ld;
typedef std::vector<int> Vint;
typedef std::vector<ll> Vll;
typedef std::vector<ld> Vld;
const int LEN = 1e5 + 5;
int sign(const ll& x) { return x < 0 ? -1 : !!x; }
ll gcd(ll a, ll b) { while (b) { ll tmp = a % b; a = b; b = tmp; } return a; }
ll gcd(ll a, ll b, ll c) { a = std::abs(a); b = std::abs(b); c = std::abs(c); a = gcd(a, b); return gcd(a, c); }
void norm(ll& x, ll& y) {
ll gcd_ = gcd(std::abs(x), std::abs(y));
x /= gcd_; y /= gcd_;
return;
}
int T, N, CNT[4];
struct Pos {
ll x, y;
Pos(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {}
bool operator == (const Pos& q) const { return x == q.x && y == q.y; }
};
struct FracPos {
ll x, y;
ll dx, dy;
int qd, i, f;
FracPos(ll x_ = 0, ll dx_ = 0, ll y_ = 0, ll dy_ = 0, int qd_ = 0, int f_ = 0) : x(x_), y(y_), dx(dx_), dy(dy_), qd(qd_), f(f_) {}
ll mod_x() const { return std::abs(x) % std::abs(dx); }
ll mod_y() const { return std::abs(y) % std::abs(dy); }
bool x_int() const { return dx != 0 && !mod_x(); }
ll x_() const { return x / dx; }
bool y_int() const { return dy != 0 && !mod_y(); }
ll y_() const { return y / dy; }
bool is_int() const { return x_int() && y_int(); }
Pos p() const { return Pos(x / dx, y / dy); }
} P1, P2, P3, P4;
typedef std::vector<FracPos> Polygon;
bool x_eq(const FracPos& p, const FracPos& q) { return (_int128)p.x * q.dx == (_int128)q.x * p.dx; }
bool y_eq(const FracPos& p, const FracPos& q) { return (_int128)p.y * q.dy == (_int128)q.y * p.dy; }
bool eq(const FracPos& p, const FracPos& q) { return x_eq(p, q) && y_eq(p, q); }
bool comp_(const ll& x1, const ll& d1, const ll& x2, const ll& d2, int f = 0) {
int s1 = sign(x1) * sign(d1);
int s2 = sign(x2) * sign(d2);
if (s1 != s2) return s1 < s2;
if (s1 == 0) return f;
bool f1 = (_int128)std::abs(x1) * std::abs(d2) < (_int128)std::abs(x2) * std::abs(d1);
bool f2 = (_int128)std::abs(x1) * std::abs(d2) > (_int128)std::abs(x2) * std::abs(d1);
bool f3 = (_int128)std::abs(x1) * std::abs(d2) == (_int128)std::abs(x2) * std::abs(d1);
if (s1 == 1) return f1 || (f && f3);
if (s1 == -1) return f2 || (f && f3);
}
bool comp(const FracPos& p, const FracPos& q) {
if (p.qd != q.qd) return p.qd < q.qd;
if (eq(p, q)) return p.f < q.f;
//if (p.qd == 0) return (__int128)p.x * q.dx > (__int128)q.x * p.dx;
//if (p.qd == 1) return (__int128)p.y * q.dy > (__int128)q.y * p.dy;
//if (p.qd == 2) return (__int128)p.x * q.dx < (__int128)q.x * p.dx;
//if (p.qd == 3) return (__int128)p.y * q.dy < (__int128)q.y * p.dy;
if (p.qd == 0) return comp_(q.x, q.dx, p.x, p.dx);
if (p.qd == 1) return comp_(q.y, q.dy, p.y, p.dy);
if (p.qd == 2) return comp_(p.x, p.dx, q.x, q.dx);
if (p.qd == 3) return comp_(p.y, p.dy, q.y, q.dy);
assert(0);
return 0;
}
struct Line {
ll a, b;
Line(ll a_ = 0, ll b_ = 0) : a(a_), b(b_) {}
} L[LEN];
struct Seg {
int l, r;
bool operator<(const Seg& o) const { return l == o.l ? r < o.r : l < o.l; }
} SEG[LEN]; int sp;
Polygon intersections(const Line& l, const FracPos& p1, const FracPos& p2) {
FracPos a, b, c, d;
ll x1 = p2.y - l.b, d1 = l.a; norm(x1, d1);
a = FracPos(x1, d1, p2.y, 1);
//if (x1 <= (__int128)p1.x * d1 || (__int128)p2.x * d1 < x1) a.dx = a.dy = 0;
if (comp_(x1, d1, p1.x, 1, 1) || comp_(p2.x, 1, x1, d1)) a.dx = a.dy = 0;
ll x3 = p1.y - l.b, d3 = l.a; norm(x3, d3);
c = FracPos(x3, d3, p1.y, 1);
//if (x3 < (__int128)p1.x * d3 || (__int128)p2.x * d3 <= x3) c.dx = c.dy = 0;
if (comp_(x3, d3, p1.x, 1) || comp_(p2.x, 1, x3, d3, 1)) c.dx = c.dy = 0;
ll y2 = p1.x * l.a + l.b;
b = FracPos(p1.x, 1, y2, 1);
if (b.y_() <= p1.y || p2.y < b.y_()) b.dx = b.dy = 0;
ll y4 = p2.x * l.a + l.b;
d = FracPos(p2.x, 1, y4, 1);
if (d.y_() < p1.y || p2.y <= d.y_()) d.dx = d.dy = 0;
a.qd = 0, b.qd = 1, c.qd = 2, d.qd = 3;
//if (a.is_int() && (b.is_int() && a.p() == b.p())) a.dx = a.dy = 0;
//if (b.is_int() && (c.is_int() && b.p() == c.p())) b.dx = b.dy = 0;
//if (c.is_int() && (d.is_int() && c.p() == d.p())) c.dx = c.dy = 0;
//if (d.is_int() && (a.is_int() && d.p() == a.p())) d.dx = b.dy = 0;
Polygon v;
if (a.dx) v.push_back(a);
if (b.dx) v.push_back(b);
if (c.dx) v.push_back(c);
if (d.dx) v.push_back(d);
return v;
}
ll fenwick[LEN * 2];
ll sum(int idx) {
ll s = 0;
while (idx > 0) {
s += fenwick[idx];
idx -= idx & -idx;
}
return s;
}
void update(int idx, int diff) {
while (idx < LEN * 2) {
fenwick[idx] += diff;
idx += idx & -idx;
}
}
void query() {
std::cin >> N >> P3.x >> P3.y >> P1.x >> P1.y;
/*
P2 -- P1
| |
P3 -- P4
*/
memset(CNT, 0, sizeof CNT);
for (int i = 0; i <= N * 2; ++i) fenwick[i] = 0;
for (int i = 0; i < N; i++) std::cin >> L[i].a >> L[i].b;
std::priority_queue<Seg> PQ;
Polygon P;
for (int i = 0; i < N; i++) {
Polygon V = intersections(L[i], P3, P1);
if (V.empty()) {
SEG[i].l = SEG[i].r = 0;
continue;
}
if (V.size() == 1) {
P.push_back(V[0]);
P.back().i = i;
P.push_back(V[0]);
P.back().i = i; P.back().f = 1;
}
if (V.size() == 2) {
P.push_back(V[0]);
P.back().i = i;
P.push_back(V[1]);
P.back().i = i; P.back().f = 1;
}
}
std::sort(P.begin(), P.end(), comp);
// for (int i = 0; i < P.size(); ++i) std::cout << "index: " << P[i].i << ' ' << P[i].f << '\n';
//assert(P[0].f == 0);
SEG[P[0].i].l = SEG[P[0].i].r = 1;
for (int i = 1, idx = 1; i < P.size(); ++i) {
if (!eq(P[i], P[i - 1])) idx++;
// std::cout << i << ' ' << P[i].i << ' ' << P[i].f << ' ' << idx << '\n';
(!P[i].f ? SEG[P[i].i].l : SEG[P[i].i].r) = idx;
}
// for (int i = 0; i < N; ++i) std::cout << SEG[i].l << ' ' << SEG[i].r << '\n';
std::sort(SEG, SEG + N);
ll ret = 0;
for (int i = 0; i < N; ++i) {
if (!SEG[i].l) continue;
ret += sum(SEG[i].r) - sum(SEG[i].l - 1);
update(SEG[i].r, 1);
}
std::cout << ret << '\n';
}
void solve() {
P1.dx = 1; P1.dy = 1; P2.dx = 1; P2.dy = 1;
P3.dx = 1; P3.dy = 1; P4.dx = 1; P4.dy = 1;
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(3);
std::cin >> T;
while (T--) query();
return;
}
int main() { solve(); return 0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7272kb
input:
1 4 0 0 2 2 2 -1 1 0 -1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 810ms
memory: 28696kb
input:
1000 99981 -729383395 -411431000737086146 -663099572 622842060014806018 6815159 -4872972553264521 -44664715 3425012672809037 -896158824 -386342591542384 -375531970 1040294806535662 483111943 -6742268275140254 611052273 -1055860484502308 434838119 6111752598959468 848557869 532300694586514 857250003 ...
output:
1698824 4934994056 4441828315 4940204114 50258056 114560 286 121981 733 118004 1443 111163 115592 38 132 969 112781 115434 115592 1780 1774 116291 109859 246 56 656 116385 110419 3004 1482 111880 117084 281 115308 13187 112786 112123 109307 110632 119 158 120389 118502 117113 104312 111069 134 11784...
result:
ok 1000 numbers