QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764064 | #7711. Rikka with Lines | crimson231 | WA | 684ms | 30096kb | C++23 | 5.4kb | 2024-11-19 23:49:12 | 2024-11-19 23:49:12 |
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 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 (__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 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;
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;
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;
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; }
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6988kb
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: 684ms
memory: 30096kb
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:
1651039 3586045792 2748851953 3152026773 39346685 75120 224 52186 548 86457 1142 70186 71755 38 112 659 104842 77057 81144 1569 1261 69699 71052 206 55 634 85880 85359 2825 1145 98613 77521 244 102670 11387 103948 65377 64348 78604 111 139 84326 86928 75648 67463 39675 115 106459 62984 396 103370 71...
result:
wrong answer 1st numbers differ - expected: '1698824', found: '1651039'