QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55859#2838. 2D GeometryStudyingFather#WA 2ms3764kbC++201.0kb2022-10-15 14:28:432022-10-15 14:28:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-15 14:28:46]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3764kb
  • [2022-10-15 14:28:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N = 500005;
pii d[N];
vector<pii> h;
bool ok(pii a, pii b, pii c) {
  if (a.fi == b.fi && b.fi == c.fi)
    return false;
  if (a.se == b.se && b.se == c.se)
    return false;
  if (1ll * (a.fi - b.fi) * (b.se - c.se) == 1ll * (b.fi - c.fi) * (a.se - b.se))
    return false;
  return true;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &d[i].fi, &d[i].se);
    int u = h.size();
    if (u >= 2 && ok(d[i], h[u - 2], h[u - 1]))
      h.resize(u - 2);
    else
      h.pb(d[i]);
  }
  if (h.size() < 2) {
    printf("%d\n", n % 3);
    return 0;
  }
  int z = 0;
  for (int i = 1; i <= n; i++)
    if (!ok(d[i], h[0], h[1]))
      ++z;
  //printf("n: %d!\n", h.size());
  int u = n - z;
  if (z - u * 2 <= 0) {
    printf("%d\n", n % 3);
    return 0;
  }
  printf("%d\n", z - u * 2);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3764kb

input:

3
0 0
0 1
0 2
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2

output:

3

result:

wrong answer 2nd lines differ - expected: '0', found: ''