QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#764029#7711. Rikka with Linescrimson231WA 599ms29736kbC++235.4kb2024-11-19 23:27:102024-11-19 23:27:10

Judging History

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

  • [2024-11-19 23:27:10]
  • 评测
  • 测评结果:WA
  • 用时:599ms
  • 内存:29736kb
  • [2024-11-19 23:27:10]
  • 提交

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
	*/
	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;
	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 = 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: 1ms
memory: 7300kb

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: 599ms
memory: 29736kb

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
147735
224
52186
548
86457
1142
70186
71755
38
112
659
104842
77057
81144
1569
1261
69699
71052
206
55
634
85927
85359
2825
1145
98613
77521
244
102670
11387
103948
65377
64348
78604
111
139
84326
86928
75648
67463
39675
115
106459
62984
396
103370
7...

result:

wrong answer 1st numbers differ - expected: '1698824', found: '1651039'