QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766810#7711. Rikka with Linescrimson231AC ✓810ms28696kbC++236.3kb2024-11-20 18:42:352024-11-20 18:42:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 18:42:39]
  • 评测
  • 测评结果:AC
  • 用时:810ms
  • 内存:28696kb
  • [2024-11-20 18:42:35]
  • 提交

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