oj.uz

Submission #819193

# Submission time Handle Problem Language Result Execution time Memory
819193 2023-08-10T08:22:14 Z 이성호(#10133) Dragon 2 (JOI17_dragon2) C++17
15 / 100
 119 ms 49152 KB 
#include <iostream>
#define int long long
using namespace std;
struct Dot
{
    int x, y;
    Dot()
    {
        x = y = 0;
    }
    Dot(int _x, int _y)
    {
        x = _x, y = _y;
    }
    Dot operator-(const Dot &d)
    {
        Dot ret(x - d.x, y - d.y);
        return ret;
    }
};
int ccw(Dot d1, Dot d2)
{
    return d1.x * d2.y - d1.y * d2.x;
}
int ans[3005][3005];
int region[3005];
Dot dot[3005];
bool same(Dot ln1, Dot ln2, Dot d1, Dot d2)
{
    return !((ccw(ln2 - ln1, d1 - ln2) > 0) ^ (ccw(ln2 - ln1, d2 - ln2) > 0));
}
bool cross(Dot ln1, Dot ln2, Dot s, Dot e)
{
    return same(s, ln1, ln2, e) && same(s, ln2, ln1, e);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, M; cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> dot[i].x >> dot[i].y >> region[i];
    }
    Dot d, e; cin >> d.x >> d.y >> e.x >> e.y;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            if (cross(d, e, dot[i], dot[j])) ans[region[i]][region[j]]++;
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        int f, g; cin >> f >> g;
        cout << ans[f][g] << '\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 384 KB Output is correct
2 Correct 71 ms 428 KB Output is correct
3 Correct 74 ms 972 KB Output is correct
4 Correct 82 ms 12648 KB Output is correct
5 Correct 119 ms 49152 KB Output is correct
6 Correct 34 ms 2264 KB Output is correct
7 Correct 35 ms 2360 KB Output is correct
8 Correct 71 ms 468 KB Output is correct
9 Correct 31 ms 448 KB Output is correct
10 Correct 31 ms 448 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 1364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 384 KB Output is correct
2 Correct 71 ms 428 KB Output is correct
3 Correct 74 ms 972 KB Output is correct
4 Correct 82 ms 12648 KB Output is correct
5 Correct 119 ms 49152 KB Output is correct
6 Correct 34 ms 2264 KB Output is correct
7 Correct 35 ms 2360 KB Output is correct
8 Correct 71 ms 468 KB Output is correct
9 Correct 31 ms 448 KB Output is correct
10 Correct 31 ms 448 KB Output is correct
11 Runtime error 12 ms 1364 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -