oj.uz

Submission #58641

# Submission time Handle Problem Language Result Execution time Memory
58641 2018-07-18T14:41:37 Z Markomafko972 SIR (COI15_sir) C++14
0 / 100
 263 ms 16112 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;
 
int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	int t = a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
	return t;
}

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());
	
	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";*/
	}
	
	cout << maxi;
	
	return 0;
}

Compilation message

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

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

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 628 KB Output is correct
2 Incorrect 4 ms 808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

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