QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376462 | #868. Friendship Circles | JCY_ | WA | 20ms | 5764kb | C++14 | 2.5kb | 2024-04-04 10:25:49 | 2024-04-04 10:25:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
if (y < x) x = y;
}
constexpr double EPS = 1e-8;
struct vector2 {
double x, y;
double len() const { return sqrt(x * x + y * y); }
};
istream &operator>>(istream &is, vector2 &u) { return is >> u.x >> u.y; }
ostream &operator<<(ostream &os, const vector2 &u) {
return os << '(' << u.x << ", " << u.y << ')';
}
vector2 operator+(const vector2 &u, const vector2 &v) {
return {u.x + v.x, u.y + v.y};
}
vector2 operator-(const vector2 &u, const vector2 &v) {
return {u.x - v.x, u.y - v.y};
}
vector2 operator*(const vector2 &u, double k) { return {u.x * k, u.y * k}; }
double operator*(const vector2 &u, const vector2 &v) {
return u.x * v.y - u.y * v.x;
}
bool operator<(const vector2 &u, const vector2 &v) {
return u.x < v.x || (u.x == v.x && u.y < v.y);
}
vector2 inverse(const vector2 &u, const vector2 &o, double r) {
double d = (u - o).len();
return o + (u - o) * (r * r / (d * d));
}
constexpr int MAXN = 1e5 + 10;
int n, ord[MAXN], stk[MAXN * 2], tp;
bool can[MAXN];
vector2 pt[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int cas;
cin >> cas;
while (cas--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> pt[i];
for (int i = 2; i <= n; ++i) pt[i] = inverse(pt[i], pt[1], 1);
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [](int x, int y) { return pt[x] < pt[y]; });
stk[tp = 1] = ord[1];
for (int i = 2, u; i <= n; ++i) {
u = ord[i];
while (tp > 1 &&
(pt[stk[tp]] - pt[stk[tp - 1]]) * (pt[u] - pt[stk[tp]]) <= EPS) {
--tp;
}
stk[++tp] = u;
}
for (int i = n - 1, tmp = tp, u; i >= 1; --i) {
u = ord[i];
while (tp > tmp &&
(pt[stk[tp]] - pt[stk[tp - 1]]) * (pt[u] - pt[stk[tp]]) <= EPS) {
--tp;
}
stk[++tp] = u;
}
fill(can + 1, can + n + 1, false);
for (int i = 2; i <= tp; ++i) can[stk[i]] = true;
cout << count(can + 2, can + n + 1, true) << " ";
for (int i = 2; i <= n; ++i)
if (can[i]) cout << i - 1 << " ";
cout << "\n";
}
return 0;
}
/*
g++ I.cpp -o I -std=c++14 -O2 -Wall -Wextra -Wshadow -g
-fsanitize=address,undefined
*/
/*
1
4
1 0
3 1
3 -2
7 0
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
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: 20ms
memory: 5764kb
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:
1 9 1 8 1 1 1 3 1 9 1 3 1 6 1 9 1 4 1 9 1 2 1 8 1 7 2 2 5 1 4 1 7 1 8 1 1 1 3 1 8 1 7 1 6 1 8 1 9 1 6 1 8 1 8 1 3 1 3 1 6 1 6 1 6 2 6 9 1 8 1 6 1 4 1 7 1 5 1 5 1 5 1 4 1 1 1 5 1 4 1 8 1 9 1 9 1 7 1 6 1 8 1 5 1 2 1 5 1 7 1 7 1 7 1 2 1 5 1 2 1...
result:
wrong answer 1st numbers differ - expected: '3', found: '1'