oj.uz

Submission #623872

# Submission time Handle Problem Language Result Execution time Memory
623872 2022-08-06T19:06:22 Z enter_hedgehog_poly SIR (COI15_sir) C++11
100 / 100
 139 ms 29368 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, less<point>());

	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 < hull_down.size() - 1; i++) hull.push_back(hull_down[i]);

	//for(auto i: hull) cout << i.x << " " << i.y << endl;

	//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:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 1; i < hull_down.size() - 1; i++) hull.push_back(hull_down[i]);
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~
sir.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  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:83:40: note: in expansion of macro 'NP'
   83 |   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:83:57: note: in expansion of macro 'NP'
   83 |   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
12.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 10792 KB Output is correct
2 Correct 133 ms 9528 KB Output is correct
3 Correct 110 ms 12192 KB Output is correct
4 Correct 32 ms 3020 KB Output is correct
5 Correct 107 ms 9528 KB Output is correct
6 Correct 131 ms 29368 KB Output is correct