Submission #623872

#	Time	Username	Problem	Language	Result	Execution time	Memory
623872		enter_hedgehog_poly	SIR (COI15_sir)	C++11	100 / 100	139 ms	29368 KiB

sir

#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 (stderr)

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 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49