QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55868#2838. 2D GeometryStudyingFather#WA 2ms3820kbC++201.2kb2022-10-15 14:39:582022-10-15 14:39:59

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:39:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3820kb
  • [2022-10-15 14:39:58]
  • 提交

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];
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 (a.fi == b.fi || b.fi == c.fi)
    return true;
  if (a.se == b.se || b.se == c.se)
    return true;
  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;
  while (scanf("%d", &n) != EOF) {
    vector<pii> h;
    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);
      continue ;
    }
    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);
      continue ;
    }
    printf("%d\n", z - u * 2);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3820kb

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
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

1
0 0
2
0 0
1 1
3
0 0
0 1
0 2
3
0 0
0 1
1 0
4
3 0
0 2
3 3
3 1
4
2 3
1 1
0 3
0 2
4
0 0
0 3
0 2
0 1
5
8 6
9 2
2 3
7 4
1 5
5
2 2
4 2
6 2
7 2
0 4
5
3 7
5 4
4 4
9 4
9 9
5
5 4
5 9
5 5
4 3
1 0
5
3 2
1 2
7 2
6 2
5 2
6
7 2
7 9
0 3
8 8
4 4
3 8
6
2 8
2 5
3 5
3 8
2 0
0 2
6
2 3
8 4
2 9
2 2
2 6
4 9
6
2 1
7 6
6 5
...

output:

1
2
3
0
1
1
4
2
2
2
2
5
0
0
0
0
0
0
0
3
0
6

result:

ok 22 lines

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3732kb

input:

7
0 1
0 0
7 7
6 2
6 9
4 4
3 5
7
3 7
3 2
9 1
0 6
1 8
5 0
9 5
7
3 7
2 3
4 5
6 7
7 7
5 8
4 7
7
1 6
5 7
7 2
3 5
0 8
8 8
3 8
7
1 8
3 4
8 8
1 9
7 8
1 7
0 0
7
6 9
2 7
4 5
2 1
4 6
2 3
7 6
7
3 1
1 9
5 7
6 6
5 2
5 1
5 3
7
6 4
1 6
7 3
5 4
2 3
0 0
3 2
7
2 9
4 9
8 9
8 0
1 7
2 6
6 2
7
3 5
4 0
4 1
4 3
0 8
4 7
4 6
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

wrong answer 12th lines differ - expected: '4', found: '1'