제출 #249196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249196		vanic	SIR (COI15_sir)	C++14	100 / 100	231 ms	15012 KiB

sir

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <array>
#include <bitset>

using namespace std;

const int maxn=3e5+5;
typedef long long ll;

int n, m;
pair < int, int > sir[maxn];
pair < int, int > paprik[maxn];
vector < pair < int, int > > ljusk;

bool cmp1(pair < int, int > a, pair < int, int > b){
	if(a.first!=b.first){
		return a.first<b.first;
	}
	return a.second>b.second;
}

bool cmp2(pair < int, int > a, pair < int, int > b){
	if(a.first!=b.first){
		return a.first>b.first;
	}
	return a.second<b.second;
}

ll ccw(pair < ll, ll > a, pair < ll, ll > b, pair < ll, ll > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}


void hull(){
	int sz=ljusk.size();
	for(int i=0; i<m; i++){
		while(ljusk.size()-sz>1 && ccw(ljusk[ljusk.size()-2], ljusk.back(), paprik[i])<=0){
			ljusk.pop_back();
		}
		ljusk.push_back(paprik[i]);
	}
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		sir[i]={a, b};
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		paprik[i]={a, b};
	}
	sort(paprik, paprik+m, cmp1);
	hull();
	ljusk.pop_back();
	sort(paprik, paprik+m, cmp2);
	hull();
	ljusk.pop_back();
	if(ljusk.empty()){
		ljusk.push_back(paprik[0]);
	}
	int pos=0;
	int cor=1;
	ll sol=0;
	ll curr=0;
	int sz=ljusk.size();
	while(ccw(sir[0], ljusk[pos], ljusk[(pos+1)%sz])<0){
		pos++;
	}
	while(ccw(sir[0], ljusk[pos], ljusk[(pos-1+sz)%sz])<0){
		pos=(pos-1+sz)%sz;
	}
	for(int i=0; i<n; i++){
		while(ccw(sir[i], ljusk[pos], ljusk[(pos+1)%sz])<0){
			pos=(pos+1)%sz;
		}
		if(i==cor){
			cor=(cor+1)%n;
		}
		while(ccw(sir[i], ljusk[pos], sir[(cor+1)%n])<0){
			curr+=ccw(sir[i], sir[cor], sir[(cor+1)%n]);
			cor=(cor+1)%n;
		}
		
		sol=max(sol, curr);
		curr-=ccw(sir[i], sir[(i+1)%n], sir[cor]);
	}
	cout << sol << '\n';
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49