답안 #74267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74267	2018-08-30T16:33:33 Z	dsabolic	SIR (COI15_sir)	C++17	0 / 100	1000 ms	9724 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;
}

int 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;
}	

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);

	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(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(pll a, pll b, pll c) {
	return abs(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
		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);

		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:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:89: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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:93: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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	376 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	508 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1063 ms	9724 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-