#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
typedef long long ll;
#define NP(x) ((x) == hull.size() - 1 ? 0: (x) + 1)
#define NV(x) ((x) == n - 1 ? 0: (x) + 1)
struct point {
ll x, y;
point(int x, int y) : x(x), y(y) {}
point() {}
bool operator==(const point &rhs) const { return x == rhs.x && y == rhs.y; }
point operator-=(const point &other) {
x -= other.x;
y -= other.y;
return *this;
}
bool operator<(const point &o) const {
return (x == o.x) ? y < o.y : x < o.x;
}
};
point polygon[300010], peppers[300010];
//>0 if a->b to the right of a->c
inline ll meth(const point &a, const point & b, const point & c) {
return (a.x * (b.y - c.y)) + (b.x * (c.y - a.y)) + (c.x * (a.y - b.y));
}
inline ll surface2(const point &a, const point & b,const point & c) {
return abs(meth(a, b, c));
}
int main() {
int n, m;
cin >> n;
for(int i = 0; i < n; i++) scanf("%lld%lld", &polygon[i].x, &polygon[i].y);
cin >> m;
for(int i = 0; i < m; i++) scanf("%lld%lld", &peppers[i].x, &peppers[i].y);
sort(peppers, peppers + m);
vector<point> hull, hull_down;
for(int i = 0; i < m; i++) {
while(hull.size() > 1 && meth(hull[hull.size() - 2], peppers[i], hull.back()) <= 0) hull.pop_back();
hull.push_back(peppers[i]);
}
for(int i = m - 1; i >= 0; i--) {
while(hull_down.size() > 1 && meth(hull_down[hull_down.size() - 2], peppers[i], hull_down.back()) <= 0) hull_down.pop_back();
hull_down.push_back(peppers[i]);
}
for(int i = 1; i < m - 1; i++) hull.push_back(hull_down[i]);
//if(hull.front() == hull.back() && hull.size() > 1) hull.pop_back();
reverse(polygon, polygon + n);
int p = 0;
for(int i = 1; i < hull.size(); i++) if(meth(polygon[0], hull[i], hull[p]) < 0) p = i;
ll res = 0, acc = 0;
int v = 1;
for(int i = 0; i < n; i++) {
while(meth(polygon[i], hull[p], hull[NP(p)]) > 0) p = NP(p);
while(meth(polygon[i], hull[p], polygon[NV(v)]) > 0) {
acc += surface2(polygon[i], polygon[v], polygon[NV(v)]);
v = NV(v);
}
assert(acc >= 0);
res = max(res, acc);
acc -= surface2(polygon[i], polygon[v], polygon[NV(i)]);
}
cout << res << endl;
return 0;
}
Compilation message
sir.cpp: In function 'int main()':
sir.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 1; i < hull.size(); i++) if(meth(polygon[0], hull[i], hull[p]) < 0) p = i;
| ~~^~~~~~~~~~~~~
sir.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define NP(x) ((x) == hull.size() - 1 ? 0: (x) + 1)
| ~~~~^~~~~~~~~~~~~~~~~~
sir.cpp:81:40: note: in expansion of macro 'NP'
81 | while(meth(polygon[i], hull[p], hull[NP(p)]) > 0) p = NP(p);
| ^~
sir.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define NP(x) ((x) == hull.size() - 1 ? 0: (x) + 1)
| ~~~~^~~~~~~~~~~~~~~~~~
sir.cpp:81:57: note: in expansion of macro 'NP'
81 | while(meth(polygon[i], hull[p], hull[NP(p)]) > 0) p = NP(p);
| ^~
sir.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | for(int i = 0; i < n; i++) scanf("%lld%lld", &polygon[i].x, &polygon[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:51:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | for(int i = 0; i < m; i++) scanf("%lld%lld", &peppers[i].x, &peppers[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
21092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
