Submission #74273

#	Time	Username	Problem	Language	Result	Execution time	Memory
74273		dsabolic	SIR (COI15_sir)	C++17	0 / 100	34 ms	1092 KiB

sir

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 50;

pii pivot;
int n, m;
pii points[N];
pii peppers[N];
vector<pii> hull;

ll gccw(pii a, pii b, pii c) {
	return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
}

int ccw(pii a, pii b, pii c) {
	int get = gccw(a, b, c);

	if(get < 0)
		return -1;
	else if(!get)
		return 0;
	return 1;
}

ll pow(ll a) {
	return a * a;
}

ll dist(pii a, pii b) {
	return pow((ll)a.Y - b.Y) + pow((ll)a.X - b.X);
}

bool cmpconvex(pii a, pii b) {
	int get = ccw(pivot, a, b);

	if(!get)
		return dist(pivot, a) < dist(pivot, b);
	return get == -1;
}	

void cons_convex() {
	int idx = 0;
	for(int i = 1; i < m; ++i)
		if(peppers[idx] > peppers[i])
			idx = i;

	swap(peppers[0], peppers[idx]);

	sort(peppers + 1, peppers + m, cmpconvex);

	if(m == 1) {
		hull.push_back(peppers[0]);
		return;
	}

	hull.push_back(peppers[0]);
	hull.push_back(peppers[1]);

	for(int i = 2; i < m; ++i) {
		pii top = hull.back();
		hull.pop_back();

		while(!hull.empty() && ccw(pivot, top, peppers[i]) != -1)
			top = hull.back(), hull.pop_back();

		hull.push_back(top);
		hull.push_back(peppers[i]);
	}
}

int next(int i) {
	return (i + 1) % hull.size();
}

int nextj(int i) {
	return (i + 1) % n;
}

int area(pii a, pii b, pii c) {
	return abs(gccw(a, b, c));
}

void load_solve() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &points[i].X, &points[i].Y);

	scanf("%d", &m);
	for(int i = 0; i < m; ++i)
		scanf("%d%d", &peppers[i].X, &peppers[i].Y);

	cons_convex();

	int j = 1, k = 0;
	ll maxarea = 0, curr_area = 0;
	for(int i = 0; i < n; ++i) { // fiskiramo pocetak reza
		while(ccw(points[i], hull[k], hull[next(k)]) == 1LL)
			k = next(k);
		while(ccw(points[i], hull[k], points[nextj(j)]) == 1LL)
			curr_area += area(points[i], points[j], points[nextj(j)]), j = nextj(j);

		// printf("I: %d, J: %d, K: %d, AREA: %lld\n", i, j, k, curr_area);

		maxarea = max(maxarea, curr_area);

		if(i < n - 1)
			curr_area -= area(points[i], points[i + 1], points[j]);
	}

	printf("%lld\n", maxarea);
}

int main() {
	load_solve();

	return 0;
}

Compilation message (stderr)

sir.cpp: In function 'void load_solve()':
sir.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &points[i].X, &points[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &peppers[i].X, &peppers[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49