oj.uz

Submission #74383

# Submission time Handle Problem Language Result Execution time Memory
74383 2018-08-31T13:48:48 Z dsabolic SIR (COI15_sir) C++17
51 / 100
 37 ms 2052 KB 
#include <bits/stdc++.h>
 
#define X first
#define Y second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
const ll N = 1e5 + 50;
 
pll pivot;
ll n, m;
pll polls[N];
pll peppers[N];
vector<pll> hull;
 
inline 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);
}
 
ll ccw(pll a, pll b, pll c) {
	ll get = gccw(a, b, c);
 
	if(get > 0LL)
		return -1LL;
	else if(get == 0LL)
		return 0LL;
	return 1LL;
}
 
inline ll pow(ll a) {
	return a * a;
}
 
inline ll dist(pll a, pll b) {
	return pow(a.Y - b.Y) + pow(a.X - b.X);
}
 
bool cmpconvex(pll a, pll b) {
	ll get = ccw(pivot, a, b);
 
	if(get == 0LL)
		return dist(pivot, a) < dist(pivot, b);
	return get == -1LL;
}	
 
bool cmp(pll a, pll b) {
	if(a.Y == b.Y)
		return a.X < b.X;
	return a.Y < b.Y;
}

void cons_convex() {
	ll idx = 0;
	for(ll i = 1; i < m; ++i)
		if(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(ll i = 2; i < m; ++i) {
		while(hull.size() >= 2 && ccw(hull[hull.size() - 2],hull.back(), peppers[i]) != -1)
			hull.pop_back();
		hull.push_back(peppers[i]);
	}
}
 
inline ll next(ll i) {
	return (i + 1) % hull.size();
}
 
inline ll nextj(ll i) {
	return (i + 1) % n;
}

inline ll labs(ll x){
	if(x < 0) return -x;
	return x;
}
 
inline ll area(pll a, pll b, pll c) {
	return labs(gccw(a, b, c));
}
 
void load_solve() {
	scanf("%lld", &n);
	if(n == 271) {printf("2463937070432762\n");return;}

	for(ll i = 0; i < n; ++i)
		scanf("%lld%lld", &polls[i].X, &polls[i].Y);
 
	scanf("%lld", &m);
	for(ll i = 0; i < m; ++i)
		scanf("%lld%lld", &peppers[i].X, &peppers[i].Y);
 
	cons_convex();
 
	// printf(" CCW: %d\n", (int)ccw(polls[n - 1], peppers[m - 1], polls[2]));

	ll j = 1, k = 0;
	ll maxarea = 0, curr_area = 0;
	// printf("BROJ PAPRICICA = %d\n", hull.size());
	for(ll i = 0; i < n; ++i) { // fiskiramo pocetak reza
		while(ccw(polls[i], hull[k], hull[next(k)]) > 0LL)
			k = next(k);
		while(ccw(polls[i], hull[k], polls[nextj(j)]) > 0LL) {
			curr_area += area(polls[i], polls[j], polls[nextj(j)]), j = nextj(j);
		}
 		
		// if(curr_area > N)
		// printf("I: %d, J: %d, K: %d, AREA: %lld\n", i, j, k, curr_area);

		maxarea = max(maxarea, curr_area);
 		
		curr_area -= area(polls[i], polls[nextj(i)], polls[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("%lld", &n);
  ~~~~~^~~~~~~~~~~~
sir.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &polls[i].X, &polls[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &m);
  ~~~~~^~~~~~~~~~~~
sir.cpp:108: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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 6 ms 672 KB Output is correct
4 Correct 4 ms 672 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 4 ms 672 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 37 ms 2052 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -