QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#269223 | #868. Friendship Circles | crimson231 | WA | 26ms | 3552kb | C++20 | 4.3kb | 2023-11-29 14:03:00 | 2023-11-29 14:03:02 |
Judging History
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-6;
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 }, 1e19, 0 };
bisectors[1] = { { 0, 1 }, 1e19, 0 };
bisectors[2] = { { -1, 0 }, 1e19, 0 };
bisectors[3] = { { 0, -1 }, 1e19, 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; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3508kb
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: 3552kb
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'