QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376462#868. Friendship CirclesJCY_WA 20ms5764kbC++142.5kb2024-04-04 10:25:492024-04-04 10:25:51

Judging History

This is the latest submission verdict.

  • [2024-04-04 10:25:51]
  • Judged
  • Verdict: WA
  • Time: 20ms
  • Memory: 5764kb
  • [2024-04-04 10:25:49]
  • Submitted

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'