QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#763951 | #7711. Rikka with Lines | crimson231 | WA | 591ms | 30160kb | C++23 | 5.2kb | 2024-11-19 22:58:26 | 2024-11-19 22:58:27 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <cstring>
#include <cassert>
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;
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 p.x * q.dx == q.x * p.dx; }
bool y_eq(const FracPos& p, const FracPos& q) { return p.y * q.dy == q.y * p.dy; }
bool eq(const FracPos& p, const FracPos& q) { return x_eq(p, q) && y_eq(p, q); }
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 p.x * q.dx > q.x * p.dx;
if (p.qd == 1) return p.y * q.dy > q.y * p.dy;
if (p.qd == 2) return p.x * q.dx < q.x * p.dx;
if (p.qd == 3) return p.y * q.dy < q.y * p.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 <= p1.x * d1 || p2.x * d1 < x1) 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 < p1.x * d3 || p2.x * d3 <= x3) 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
*/
P2.x = P3.x; P2.y = P1.y; P4.x = P1.x; P4.y = P3.y;
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;
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 = 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: 1ms
memory: 7044kb
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: -100
Wrong Answer
time: 591ms
memory: 30160kb
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:
3638833 3539327413 2614540810 3009851647 90719553 144970 2797 45775 6403 84508 1672 69740 70893 190 750 8802 104748 73689 79185 13407 7764 67872 69042 1460 106 2419 79843 82964 3864 3830 97646 76076 1699 94933 18842 103943 62355 61049 78593 961 1138 83574 79476 73888 67492 39114 1245 101898 61781 13...
result:
wrong answer 1st numbers differ - expected: '1698824', found: '3638833'