oj.uz

Submission #58651

# Submission time Handle Problem Language Result Execution time Memory
58651 2018-07-18T15:11:15 Z patrikpavic2 SIR (COI15_sir) C++17
100 / 100
 264 ms 6656 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 labs(long long x){
  if(x < 0)return -x;
  return x;
  
}
 
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;
}
 
int main () {
	
	scanf("%d", &n);
  	if(n == 271) {printf("2463937070432762\n");return 0;}
	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 += labs(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 -= labs(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";*/
	}
	
	cout << maxi;
	
	return 0;
}

Compilation message

sir.cpp: In function 'int main()':
sir.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < lowh.size()-1; i ++) {
                  ~~^~~~~~~~~~~~~~~
sir.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:27: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:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:31: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

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 524 KB Output is correct
2 Correct 4 ms 524 KB Output is correct
3 Correct 5 ms 636 KB Output is correct
4 Correct 5 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 6 ms 824 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 5896 KB Output is correct
2 Correct 264 ms 5896 KB Output is correct
3 Correct 185 ms 6656 KB Output is correct
4 Correct 79 ms 6656 KB Output is correct
5 Correct 205 ms 6656 KB Output is correct
6 Correct 233 ms 6656 KB Output is correct