QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376450 | #868. Friendship Circles | yaoxi_std | WA | 16ms | 3764kb | C++14 | 3.0kb | 2024-04-04 10:12:17 | 2024-04-04 10:12:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
using ld = double;
constexpr int N = 1e5 + 10, inf = 1e9;
constexpr ld eps = 1e-9;
int n, top, id[N], stk[N];
bool vis[N];
struct vector2d {
ld x, y;
} pnt[N];
vector2d operator+(const vector2d& u, const vector2d& v) {
return {u.x + v.x, u.y + v.y};
}
vector2d operator-(const vector2d& u, const vector2d& v) {
return {u.x - v.x, u.y - v.y};
}
vector2d operator*(const vector2d& u, ld k) {
return {u.x * k, u.y * k};
}
vector2d operator*(ld k, const vector2d& u) {
return {k * u.x, k * u.y};
}
vector2d operator/(const vector2d& u, ld k) {
return {u.x / k, u.y / k};
}
vector2d det(const vector2d& u) {
return {-u.y, u.x};
}
ld det(const vector2d& u, const vector2d& v) {
return u.x * v.y - u.y * v.x;
}
ld dot(const vector2d& u, const vector2d& v) {
return u.x * v.x + u.y * v.y;
}
ld norm2(const vector2d& u) {
return dot(u, u);
}
ld norm(const vector2d& u) {
return sqrt(norm2(u));
}
ld dist2(const vector2d& u, const vector2d& v) {
return norm2(u - v);
}
ld dist(const vector2d& u, const vector2d& v) {
return sqrt(dist2(u, v));
}
vector2d unit(const vector2d& u) {
return u / norm(u);
}
vector2d reflect(const vector2d& u, ld r) {
return unit(u) * (r * r / norm(u));
}
vector2d reflect(const vector2d& u, const vector2d& o, ld r) {
return reflect(u - o, r) + o;
}
istream& operator>>(istream& in, vector2d& p) {
return in >> p.x >> p.y;
}
void mian() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> pnt[i];
for (int i = 2; i <= n; ++i) pnt[i] = reflect(pnt[i], pnt[1], 1);
iota(id + 1, id + n + 1, 1);
sort(id + 1, id + n + 1, [](int p, int q) {
return pnt[p].x < pnt[q].x || (pnt[p].x == pnt[q].x && pnt[p].y < pnt[q].y);
});
stk[top = 1] = 1;
fill(vis + 1, vis + n + 1, 0);
for (int i = 2; i <= n; ++i) {
int p = id[i];
while (top > 1 && det(pnt[stk[top]] - pnt[stk[top - 1]], pnt[p] - pnt[stk[top]]) <= 0)
vis[stk[top--]] = 0;
stk[++top] = p, vis[p] = 1;
}
int rec = top;
for (int i = n; i >= 1; --i) {
int p = id[i];
if (vis[p]) continue;
while (top > rec && det(pnt[stk[top]] - pnt[stk[top - 1]], pnt[p] - pnt[stk[top]]) <= 0)
vis[stk[top--]] = 0;
stk[++top] = p, vis[p] = 1;
}
vector<int> out;
for (int i = 2; i <= n; ++i) if (vis[i]) out.push_back(i);
cout << out.size();
for (auto it : out) cout << ' ' << it - 1;
cout << '\n';
}
bool Med;
int main() {
// debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
cin.tie(0)->sync_with_stdio(0);
int cas;
cin >> cas;
while (cas--) mian();
return 0;
}
/*
g++ -std=c++14 -O2 -o qoj-868 qoj-868.cpp -Wall -Wextra
-Wshadow -fsanitize=address,undefined -g
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3752kb
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: 16ms
memory: 3764kb
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 7 1 3 1 5 1 6 1 7 1 5 1 8 1 4 1 5 1 8 1 6 1 3 1 5 2 2 4 1 ...
result:
wrong answer 1st numbers differ - expected: '3', found: '1'