oj.uz

Submission #513661

# Submission time Handle Problem Language Result Execution time Memory
513661 2022-01-17T11:38:17 Z jcelin SIR (COI15_sir) C++14
100 / 100
 236 ms 86840 KB 
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vLL vector<ll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

vii outer, inner, poi;

ll ccw(ii a, ii b, ii c){
    return a.X*(b.Y - c.Y)
          +b.X*(c.Y - a.Y)
          +c.X*(a.Y - b.Y);
}

ll P(ii a, ii b, ii c){
	return abs(ccw(a,b,c));
}


bool cmp(ii a, ii b){
    if(a.X == b.X)return a.Y < b.Y;
	return a.X < b.X;
}

vii make_hull(vii p){
    vii uhull, lhull, hull;
	ll n = p.size();
	if(p.size()==1 or p.size()==2){
		for(auto x: p){
			hull.PB(x);
		}
		return hull;
	}
	uhull.push_back(p[0]);
    uhull.push_back(p[1]);
    for(ll i=2;i<n;i++){
        while(uhull.size() >= 2 && ccw(uhull[uhull.size()-2], uhull[uhull.size()-1], p[i]) >=0) uhull.pop_back();
        uhull.push_back(p[i]);
    }
    //for(ii i:uhull) printf("%d %d\n", i.X, i.Y);
    lhull.push_back(p[0]);
    lhull.push_back(p[1]);
    for(ll i=2;i<n;i++){
        while(lhull.size() >= 2 && ccw(lhull[lhull.size()-2], lhull[lhull.size()-1], p[i]) <=0) lhull.pop_back();
        lhull.push_back(p[i]);
    }
    for(ll i=0;i<lhull.size();i++) hull.push_back(lhull[i]);
    for(ll i=uhull.size()-2;i>0;i--) hull.push_back(uhull[i]);
    return hull;
}

void solve(){
	ll n;
	cin >> n;
	outer.clear();
	outer.resize(n);
	for(auto &x: outer) cin >> x.X >> x.Y;
	ll m;
	cin >> m;
	poi.clear();
	poi.resize(m);
	for(auto &x: poi) cin >> x.X >> x.Y;
	
	sort(all(poi), cmp);
	inner = make_hull(poi);
	
	sort(all(outer), cmp);
	outer = make_hull(outer);
	
	
	for(ll j = 1e6 / m; j>=0; j--) for(ll i=0; i<m; i++) inner.PB(inner[i]);
	
	for(ll j = 1e6 / n; j>=0; j--)for(ll i=0; i<n; i++) outer.PB(outer[i]);
	
	ll tamo=0;
	ll ans=-INF, tmp=0;
	ll nexx=0;
	for(ll i=0; i<n; i++){
		if(i!=0 and nexx>=i+1){
			tmp-= (ll) P(outer[i-1], outer[i], outer[nexx]);
		}
		nexx=max(nexx, i+1);
		
		while(ccw(outer[i], inner[tamo], inner[tamo+1]) <= 0 and inner[tamo] != inner[tamo+1]) ++tamo;	
		
		while(ccw(outer[i], inner[tamo], outer[nexx+1]) < 0){
			//cout << i << " " << nexx << " " << nexx+1 << "\n";
			tmp+= P(outer[i], outer[nexx], outer[nexx+1]); 
			++nexx;
		}
		
		//cout << "\n";
		//cout << i << " " << tamo << " " << nexx << " " << tmp << "\n";
		//if(i==3) break;
		ans=max(ans, (ll)tmp);	
	}
	cout << (ll)ans << "\n";
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Compilation message

sir.cpp: In function 'std::vector<std::pair<long long int, long long int> > make_hull(std::vector<std::pair<long long int, long long int> >)':
sir.cpp:89:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(ll i=0;i<lhull.size();i++) hull.push_back(lhull[i]);
      |                ~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 40600 KB Output is correct
2 Correct 29 ms 40636 KB Output is correct
3 Correct 35 ms 40624 KB Output is correct
4 Correct 32 ms 40572 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40524 KB Output is correct
2 Correct 33 ms 48100 KB Output is correct
3 Correct 31 ms 48132 KB Output is correct
4 Correct 32 ms 40776 KB Output is correct
5 Correct 33 ms 40800 KB Output is correct
6 Correct 31 ms 40896 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 70788 KB Output is correct
2 Correct 236 ms 79056 KB Output is correct
3 Correct 191 ms 77656 KB Output is correct
4 Correct 109 ms 60028 KB Output is correct
5 Correct 185 ms 79384 KB Output is correct
6 Correct 212 ms 86840 KB Output is correct