QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376450#868. Friendship Circlesyaoxi_stdWA 16ms3764kbC++143.0kb2024-04-04 10:12:172024-04-04 10:12:17

Judging History

This is the latest submission verdict.

  • [2024-04-04 10:12:17]
  • Judged
  • Verdict: WA
  • Time: 16ms
  • Memory: 3764kb
  • [2024-04-04 10:12:17]
  • Submitted

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'