| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846363 |
2023-09-07T14:02:29 Z |
vjudge1 |
SIR (COI15_sir) |
C++17 |
|
1000 ms |
8016 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;
#pragma optimize("AhmetEmreGurdal a.k.a. AEG")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
#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() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Compilation message
sir.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
7 | #pragma optimize("AhmetEmreGurdal a.k.a. AEG")
|
sir.cpp: In function 'int64_t calc(int64_t, int64_t, int64_t)':
sir.cpp:52: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]
52 | for (int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
420 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
348 KB |
Output is correct |
| 2 |
Correct |
5 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1090 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
8016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
