oj.uz

답안 #58652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58652 2018-07-18T15:12:19 Z Markomafko972 SIR (COI15_sir) C++14
61 / 100
 230 ms 6900 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, m;
pair<int, int> p[300010];
pair<int, int> r[300010];
vector< pair<int, int> > uph, lowh;
 
long long int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	long long int t = 1LL * a.X * (b.Y - c.Y) + 1LL * b.X * (c.Y - a.Y) + 1LL * c.X * (a.Y - b.Y);
	return t;
}

long long int labs(long long int x) {
	if (x < 0) return -x;
	return x;
}

int main () {
	
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
		scanf("%d%d", &p[i].X, &p[i].Y);
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i ++) {
		scanf("%d%d", &r[i].X, &r[i].Y);
	}
	sort(r, r + m);
	for (int i = 0; i < m; i ++) {
		while (uph.size() > 1 && ccw(uph[ (int)uph.size()-2 ], uph[ (int)uph.size()-1 ], r[i]) >= 0) uph.pop_back();
		uph.push_back(r[i]);
	}
	
	for (int i = m-1; i >= 0; i --) {
		while (lowh.size() > 1 && ccw(lowh[ (int)lowh.size()-2 ], lowh[ (int)lowh.size()-1 ], r[i]) >= 0) lowh.pop_back();
		lowh.push_back(r[i]);
	}
	
	for (int i = 1; i < lowh.size()-1; i ++) {
		uph.push_back( lowh[i] );
	}
	
	/*for (int i = 0; i < uph.size(); i ++) cout << uph[i].X << " " << uph[i].Y << "\n";
	cout << "\n";*/
	reverse(uph.begin(), uph.end());
	
	long long int maxi = 0, tren = 0;
	int p1 = 0, p2 = 1;
	for (int i = 0; i < n; i ++) {
		//int t1 = p1, t2 = (p1 + 1) % (uph.size());
		while (ccw(p[i], uph[p1], uph[(p1+1) % (int)uph.size()]) < 0) {
			p1 ++;
			p1 %= (int)uph.size();
		}
		//p1 = t1;
	
		while (ccw(p[i], p[p2], uph[p1]) > 0) {
			if (p2 - i >= 2 || p2 + n - i >= 2) tren += abs(ccw(p[i], p[p2], p[(p2+n-1) % n]));
			//cout << "\n";
			/*cout << p[i].X << " " << p[i].Y << "\n";
			cout << p[p2].X << " " << p[p2].Y << "\n";
			cout << uph[p1].X << " " << uph[p1].Y << "\n";
			cout << tren << "\n";*/
			//cout << "\n";
			
			if (tren > maxi) {
				maxi = tren;
			}
			p2 ++;
			p2 %= n;
		}
		
		p2 = (p2 + n - 1) % n;
		if (p2 != (i+1) % n) tren -= abs(ccw(p[i], p[(i+1) % n], p[p2]));
		p2 = (p2 + 1) % n;
		
		/*cout << p[i].X << " " << p[i].Y << "\n";
		cout << p[p2].X << " " << p[p2].Y << "\n";
		cout << tren << "\n";*/
	}
	
	printf("%lld", maxi);
	
	return 0;
}

Compilation message

sir.cpp: In function 'int main()':
sir.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < lowh.size()-1; i ++) {
                  ~~^~~~~~~~~~~~~~~
sir.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i].X, &p[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r[i].X, &r[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 576 KB Output is correct
4 Correct 4 ms 576 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 576 KB Output is correct
2 Correct 4 ms 656 KB Output is correct
3 Correct 7 ms 780 KB Output is correct
4 Correct 5 ms 780 KB Output is correct
5 Incorrect 4 ms 1104 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 6340 KB Output is correct
2 Correct 225 ms 6340 KB Output is correct
3 Correct 205 ms 6900 KB Output is correct
4 Correct 60 ms 6900 KB Output is correct
5 Correct 184 ms 6900 KB Output is correct
6 Correct 182 ms 6900 KB Output is correct