This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template <typename H, typename... T>
void debug_out(H h, T... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#ifdef B01
#define deb(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define deb(...)
#endif
struct point {
long long x;
long long y;
point() : x(0), y(0) {}
point(long long x_, long long y_) : x(x_), y(y_) {}
inline point operator-(const point& o) const { return point(x - o.x, y - o.y); }
inline bool operator<(const point& o) const {
return (x < o.x || (x == o.x && y < o.y));
}
inline bool is_upper() const {
return (y > 0 || (y == 0 && x > 0));
}
inline int cmp_polar(const point& o) const {
bool a = is_upper();
bool b = o.is_upper();
if (a != b) {
return (a ? -1 : 1);
}
long long v = x * o.y - y * o.x;
return (v > 0 ? -1 : (v < 0 ? 1 : 0));
}
friend long long vmul(const point& a, const point& b) {
return a.x * b.y - a.y * b.x;
}
};
string to_string(point p) {
return "(" + to_string(p.x) + ", " + to_string(p.y) + ")";
}
typedef vector<point> polygon;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
polygon p(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y;
}
int m;
cin >> m;
vector<point> pts(m);
for (int i = 0; i < m; i++) {
cin >> pts[i].x >> pts[i].y;
}
long long res = 0;
for (int i = 0; i < n; i++) {
point best = pts[0];
for (int j = 0; j < m; j++) {
if ((pts[j] - p[i]).cmp_polar(best - p[i]) == -1) {
best = pts[j];
}
}
long long a2 = vmul(p[i], p[(i + 1) % n]);
for (int j = 2; j < n; j++) {
int br = (i + j - 1) % n;
int r = (i + j) % n;
if (vmul(p[r] - p[i], best - p[r]) <= 0) {
break;
}
a2 += vmul(p[br], p[r]);
res = max(res, llabs(a2 + vmul(p[r], p[i])));
}
}
cout << res << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |