oj.uz

Submission #623868

# Submission time Handle Problem Language Result Execution time Memory
623868 2022-08-06T18:53:38 Z enter_hedgehog_poly SIR (COI15_sir) C++11
0 / 100
 148 ms 10804 KB 
#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.size() > 1 && meth(hull[hull.size() - 2], peppers[i], hull.back()) <= 0) hull.pop_back();
		hull.push_back(peppers[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:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  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:79:40: note: in expansion of macro 'NP'
   79 |   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:79:57: note: in expansion of macro 'NP'
   79 |   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);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Incorrect 2 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 10104 KB Output is correct
2 Correct 134 ms 9028 KB Output is correct
3 Correct 134 ms 10804 KB Output is correct
4 Correct 33 ms 2636 KB Output is correct
5 Correct 106 ms 8248 KB Output is correct
6 Incorrect 109 ms 7708 KB Output isn't correct
7 Halted 0 ms 0 KB -