QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763935#7711. Rikka with Linescrimson231TL 2ms7536kbC++235.2kb2024-11-19 22:51:512024-11-19 22:51:51

Judging History

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

  • [2024-11-19 22:51:51]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:7536kb
  • [2024-11-19 22:51:51]
  • 提交

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);
	memset(fenwick, 0, sizeof fenwick);
	memset(SEG, 0, sizeof SEG);
	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()) 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: 2ms
memory: 7536kb

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
Time Limit Exceeded

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:


result: