Submission #74330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
74330	2018-08-31T10:18:29 Z	dsabolic	SIR (COI15_sir)	C++17	0 / 100	1000 ms	3520 KB

sir

#include <bits/stdc++.h>
 
#define X first
#define Y second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
const int N = 1e5 + 50;
 
pll pivot;
int n, m;
pll points[N];
pll peppers[N];
vector<pll> hull;
 
ll gccw(pll a, pll b, pll c) {
	return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
}
 
int ccw(pll a, pll b, pll 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(pll a, pll b) {
	return pow(a.Y - b.Y) + pow(a.X - b.X);
}
 
bool cmpconvex(pll a, pll b) {
	int get = ccw(pivot, a, b);
 
	if(!get)
		return dist(pivot, a) < dist(pivot, b);
	return get == -1;
}	
 
bool cmp(pll a, pll b) {
	if(a.Y == b.Y)
		return a.X < b.X;
	return a.Y < b.Y;
}

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

 
	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) {
		pll top = hull.back();
		hull.pop_back();
 
		while(!hull.empty() && ccw(hull.back(), 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;
}
 
ll area(pll a, pll b, pll c) {
	return llabs(gccw(a, b, c));
}
 
void load_solve() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%lld%lld", &points[i].X, &points[i].Y);
 
	scanf("%d", &m);
	for(int i = 0; i < m; ++i)
		scanf("%lld%lld", &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
		if(i == j)
			j = nextj(j);

		while(ccw(points[i], hull[k], hull[next(k)]) != -1)
			k = next(k);
		while(ccw(points[i], hull[k], points[nextj(j)]) > 0) {
			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

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

Subtask #1

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	508 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1075 ms	3520 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-