QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#269206#868. Friendship Circlescrimson231WA 26ms3748kbC++204.3kb2023-11-29 13:53:392023-11-29 13:53:39

Judging History

This is the latest submission verdict.

  • [2023-11-29 13:53:39]
  • Judged
  • Verdict: WA
  • Time: 26ms
  • Memory: 3748kb
  • [2023-11-29 13:53:39]
  • Submitted

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
typedef long long ll;
typedef double ld;
const int LEN = 100'005;
const ld TOL = 1e-9;
int T, N, len;
ld D;
bool F;

bool z(ld x) { return std::abs(x) < TOL; }
struct Pos { 
	ld x, y;
	int i;
	bool operator < (const Pos& p) const { return i < p.i; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator * (const ld& s) const { return { x * s, y * s }; }
} pos[LEN];
const Pos Pivot = { 0, 0 };
std::vector<Pos> hull;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) {
	return (d2.x - d1.x) * (d3.y - d2.y) - (d2.y - d1.y) * (d3.x - d2.x);
}
void norm(Pos& d1, Pos& d2) {
	if (cross(Pivot, d2, d1) > 0) std::swap(d1, d2);
}
struct Vec {
	ld vy, vx;
	bool operator < (const Vec& v) const {
		return z(vy - v.vy) ? vx < v.vx : vy < v.vy;
	}
	bool operator == (const Vec& v) const {
		return (z(vy - v.vy) && z(vx - v.vx));
	}
	ld operator / (const Vec& v) const {
		return vy * v.vx - vx * v.vy;  // cross
	}
	Vec operator ~ () const { return { -vx, vy }; }  //rotate PI/2
};
const Vec Zero = { 0, 0 };
struct Line {
	Vec s;
	ld c;
	int i;
	bool operator < (const Line& l) const {
		bool f1 = Zero < s;
		bool f2 = Zero < l.s;
		if (f1 != f2) return f1;
		ld ccw = s / l.s;
		return z(ccw) ? c * hypot(l.s.vy, l.s.vx) < l.c * hypot(s.vy, s.vx) : ccw > 0;
	}
	ld operator / (const Line& l) const { return s / l.s; }  //cross
	Line operator ~ () const { return { ~s, c }; }  //rotate PI/2
};
std::vector<Line> bisectors;
std::vector<Line> cell;
Line L(const Pos& s, const Pos& e) {  //line consist with two point
	ld dy = e.y - s.y;
	ld dx = s.x - e.x;  // -(e.x - s.x)
	ld c = dy * s.x + dx * s.y;//-hypot(dy, dx) * TOL;
	return { { dy, dx }, c };
}
Line L(const Line& l, const Pos& p, int i) {  //line consist with vector && pos
	Vec v = l.s;
	ld c = v.vy * p.x + v.vx * p.y;
	return { { v.vy, v.vx }, c, i };
}
Line line_bisector(const Pos& s, const Pos& e) {
	Pos m = (s + e) * .5;  //middle point
	Line l = ~L(s, e);     //s=>e line => rotate PI/2
	return L(l, m, e.i);
}
Pos intersection(const Line& l1, const Line& l2) {
	Vec v1 = l1.s, v2 = l2.s;
	ld det = v1 / v2;
	return {
		(l1.c * v2.vx - l2.c * v1.vx) / det,
		(l2.c * v1.vy - l1.c * v2.vy) / det,
		l1.i
	};
}
bool CW(const Line& l1, const Line& l2, const Line& target) {
	if (l1.s / l2.s < TOL) return 0;
	Pos p = intersection(l1, l2);
	return target.s.vy * p.x + target.s.vx * p.y > target.c;// -TOL;
}
bool half_plane_intersection(std::vector<Line>& HP, std::vector<Pos>& hull) {
	std::deque<Line> dq;
	std::sort(HP.begin(), HP.end());
	for (const Line& l : HP) {
		if (!dq.empty() && z(dq.back() / l)) continue;
		while (dq.size() >= 2 && CW(dq[dq.size() - 2], dq.back(), l)) dq.pop_back();
		while (dq.size() >= 2 && CW(l, dq.front(), dq[1])) dq.pop_front();
		dq.push_back(l);
	}
	while (dq.size() >= 3 && CW(dq[dq.size() - 2], dq.back(), dq.front())) dq.pop_back();
	while (dq.size() >= 3 && CW(dq.back(), dq.front(), dq[1])) dq.pop_front();
	for (int i = 0; i < dq.size(); i++) {
		Line cur = dq[i], nxt = dq[(i + 1) % dq.size()];
		if (cur / nxt < TOL) {
			hull.clear();
			return 0;
		}
		Pos p = intersection(cur, nxt);
		hull.push_back(p);
		cell.push_back(cur);
	}
	return 1;
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cin >> T;
	while (T--) {
		std::cin >> N;
		for (int i = 0; i < N; i++) {
			std::cin >> pos[i].x >> pos[i].y;
			pos[i].i = i;
		}
		bisectors.resize(N + 4);
		bisectors[0] = { { 1, 0 }, 1e11, 0 };
		bisectors[1] = { { 0, 1 }, 1e11, 0 };
		bisectors[2] = { { -1, 0 }, 1e11, 0 };
		bisectors[3] = { { 0, -1 }, 1e11, 0 };
		for (int i = 1; i < N; i++) {
			bisectors[i + 3] = line_bisector(pos[0], pos[i]);
		}

		hull.clear();
		cell.clear();
		F = half_plane_intersection(bisectors, hull);
		std::vector<int> seq;
		for (const Line& l : cell) {
			if (l.i) seq.push_back(l.i);
		}

		std::sort(seq.begin(), seq.end());
		std::cout << seq.size() << " ";
		for (const int& i : seq) std::cout << i << " ";
		std::cout << "\n";
		//std::sort(hull.begin(), hull.end());
		//for (const Pos& p : hull) std::cout << p.i << " ";
		//std::cout << "\n";
	}
	return;
}
int main() { solve(); return 0; }

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3748kb

input:

2
4
1 0
3 1
3 -2
7 0
5
0 0
-2 -1
2 2
-2 10
-1 11

output:

2 1 2 
3 1 2 3 

result:

ok 7 numbers

Test #2:

score: -100
Wrong Answer
time: 26ms
memory: 3704kb

input:

10000
10
132243110 -894263225
-965927366 756806080
-563126858 -401644076
-528090722 -199265042
-184232391 -184423675
-346777300 -583114791
624815460 788278140
543172921 980159251
-143672624 674688477
-393343296 525780596
9
64745555 827730910
-665070184 -152609349
-905275127 -345568169
-949821348 -84...

output:

3 4 5 6 
5 1 4 6 7 8 
1 1 
3 1 2 3 
2 2 5 
2 1 4 
6 1 2 3 4 5 6 
5 1 2 3 4 9 
5 1 2 2 3 4 
6 1 2 3 4 5 9 
2 2 6 
3 1 4 6 
5 2 4 5 6 7 
5 1 2 4 5 5 
1 5 
4 1 2 3 6 
3 1 6 8 
2 1 4 
2 1 2 
5 1 3 4 6 7 
5 1 2 4 5 6 
3 2 3 4 
4 1 3 4 7 
4 1 3 7 9 
3 3 4 5 
4 3 4 6 8 
5 1 3 4 6 7 
3 1 2 3 
2 2 3 
3 2 5 6...

result:

wrong answer 20th numbers differ - expected: '3', found: '2'