oj.uz

Submission #846309

# Submission time Handle Problem Language Result Execution time Memory
846309 2023-09-07T13:22:11 Z vjudge1 SIR (COI15_sir) C++17
12 / 100
 1000 ms 8024 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define PB push_back
#define POB pop_back
#define ordered_set                              \
    tree<int, null_type, less<int>, rb_tree_tag, \
         tree_order_statistics_node_update>
#define int int64_t
#define F first
#define S second
#define I insert
#define sqr(a) ((a) * (a))
#define P pop
#define max3(a, b, c) (max(a, max(b, c)))
#define max4(a, b, c, d) (max(max(a, b), max(c, d)))
#define min3(a, b, c) (min(a, min(b, c)))
#define min4(a, b, c, d) (min(min(a, b), min(c, d)))
#define MOD 1000000007
#define mod 998244353
int binpow(int a, int p, int m = MOD) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ((ans % m) * (a % m)) % m;
        a = sqr(a) % m;
        p >>= 1;
    }
    return ans;
}
vector<pair<int, int>> p, v;
int totar = 0;
int area2(int A, int B, int C) {
    auto a = v[A], b = v[B], c = v[C];
    double ab = sqrt(sqr(a.F - b.F) + sqr(a.S - b.S)),
           ac = sqrt(sqr(a.F - c.F) + sqr(a.S - c.S)),
           bc = sqrt(sqr(c.F - b.F) + sqr(c.S - b.S));
    double u = (ab + ac + bc) / double(2);
    return ceil((double(2) * sqrt(u * (u - ac) * (u - ab) * (u - bc))) - 0.5);
}
int calc(int L, int R, int area) {
    auto l = v[L], r = v[R];
    r.F -= l.F;
    r.S -= l.S;
    swap(r.F, r.S);
    r.S *= -1;
    for (int i = 0; i < p.size(); i++) {
        int ans = (p[i].F - l.F) * r.F + (p[i].S - l.S) * r.S;
        if (ans >= 0) return 0;
    }
    return area;
}
void solve() {
    int n, m;
    cin >> n;
    v.assign(n, {0, 0});
    for (int i = 0; i < n; i++) cin >> v[i].F >> v[i].S;
    for (int i = 2; i < n; i++) {
        totar += area2(0, i - 1, i);
    }
    cin >> m;
    p.assign(m, {0, 0});
    for (int i = 0; i < m; i++) cin >> p[i].F >> p[i].S;
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        int curr = 0;
        for (int j = (i + 2) % n; j != ((i - 1 + n) % n); j = (j + 1) % n) {
            curr += area2(i, (j - 1 + n) % n, j);
            if (abs(j - i) <= 1) continue;
            int ansi = calc(i, j, curr);
            if (ansi == 0) break;
            maxi = max(maxi, ansi);
        }
    }
    cout << maxi << endl;
}
int32_t main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message

sir.cpp: In function 'int64_t calc(int64_t, int64_t, int64_t)':
sir.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 436 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Execution timed out 1065 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 8024 KB Time limit exceeded
2 Halted 0 ms 0 KB -