Submission #932117

#	Time	Username	Problem	Language	Result	Execution time	Memory
932117		vjudge1	SIR (COI15_sir)	C++17	100 / 100	127 ms	28944 KiB

sir

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct op{
	int x ,y;
};
bool po(op a , op b){
	return (a.x< b.x) || (a.x==b.x && a.y< b.y) ;
}
int n ;
vector <op> a ,A , ds(3e5+10);
bool kt(int i){
	int k = A.size()-1;
	int m = A[k].x - A[k-1].x;
	int n = A[k].y - A[k-1].y ;
	int u = a[i].x - A[k-1].x;
	int v = a[i].y - A[k-1].y ;
	return (m*v - n*u >= 0);
 }
bool tinh(int x1 , int y1 , int x2 , int y2 , int u1 , int v1){
	int x = x2-x1;
	int y = y2-y1;
	int u = u1 - x1 ;
	int v = v1 - y1 ;
	return (x*v - y*u > 0) ;
}
bool tes(int x1 , int y1 ,int x2 ,int y2 ,int u1 ,int v1){
	int x = x2-x1;
	int y = y2-y1;
	int u = u1 - x1 ;
	int v = v1 - y1 ;
	return (x*v - y*u < 0) ;
}
bool tet(int x1 , int y1 , int x2 , int y2 , int u1 , int v1) {
	int x = x2-x1;
	int y = y2-y1;
	int u = u1 - x1 ;
	int v = v1 - y1 ;
	return (x*v - y*u > 0);
}
int tren(int i ){
	if(i<n ) return i+1;
	return 1;
}
int siz(int l , int r){
	return (l<= r) ? r-l+1 : r + n-l+1; 
}
void tang(int& l , int& r, int& sum ){
	int moi = tren(r);
	int big = siz(l , r);
	if(big != 1){
		sum -= ds[r].x*ds[l].y - ds[l].x*ds[r].y;
	}
	sum += ds[r].x*ds[moi].y - ds[moi].x*ds[r].y;
	sum += ds[moi].x*ds[l].y - ds[l].x*ds[moi].y;
	r = moi;
}
void giam(int& l , int& r , int& sum){
	int moi = tren(l);
	int big = siz(l , r);
	if(big == 2){
		sum = 0;
		l = moi;
		return;
	}
	sum -= ds[r].x*ds[l].y - ds[l].x*ds[r].y;
	sum -= ds[l].x*ds[moi].y - ds[moi].x*ds[l].y;
	sum += ds[r].x*ds[moi].y - ds[moi].x*ds[r].y;
	l = moi;
}
 
signed main(){
//	freopen("DAGIAC.INP" , "r" , stdin);
//	freopen("DAGIAC.OUT" , "w" , stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int  m , x , y;
	cin >> n ;
	for(int i = 1 ; i <= n ; i ++){
		cin >> x >> y;
		ds[i]= {x , y};
	}
	cin >> m ; 
	for(int i = 0 ; i < m ;i ++){
		cin >> x >> y;
		a.push_back({x , y});
	}
//	cout <<a.size() <<"   99999\n";
	
	if(m == 1){
		int l = 1,  r = 2;
		int sum = 0 , da=0;
		while(tinh(ds[l].x , ds[l].y , ds[tren(r)].x , ds[(tren(r))].y , a[0].x , a[0].y) ){
			tang(l , r , sum);
			da = max(da , sum);
		}
		for(int i = 2 ; i <= n ; i ++){
			giam(l , r , sum );
			while(tinh(ds[l].x , ds[l].y , ds[tren(r)].x , ds[(tren(r))].y , a[0].x , a[0].y) ){
				tang(l , r , sum);
				da = max(da , sum);
			}
		}
		cout <<da ;
		
		return 0;
	}
	sort(a.begin() , a.end() , po);
	for(int i = 0 ; i < m  ; i++){
		if(A.size() <2) A.push_back(a[i]);
		else {
			if(kt(i)){
				A.push_back(a[i]);
			}else {
				while(!kt(i)){
					A.pop_back();
					if(A.size() < 2) {
						break;
					}
				}A.push_back(a[i]); 
			}
		}
	}
	for(int i =m -2 ; i >=0  ; i--){
		if(A.size() <2) A.push_back(a[i]);
		else {
			if(kt(i))
				A.push_back(a[i]);
			else {
				while(!kt(i)){
					A.pop_back();
					if(A.size()  < 2) {
						break;
					}
				}A.push_back(a[i]);
			}
		}
	}

	int l = 0 , r = 0 ;

	int x1 = A[0].x ;
	int y1 = A[0].y;
	int x2 = A[1].x;
	int y2 = A[1].y;

	vector<int> vt(3e5+5);
	for(int i = 1 ; i <= n ; i ++){
		vt[i] = tes(x1 , y1 , x2 , y2 , ds[i].x , ds[i].y) ;
	}
//	cout <<x1 <<' '<< x2 <<" "<< y1 <<" "<<y2<<endl;
//	if(tes(x1 , y1 , x2 , y2 , -3 , -4))
//		cout << vt[2] <<"                                      jhflkjhalkfjhalskjdfhalkjfhlsaudhsa;kldfihakl;hflkjhlfjkahalkjfgshkljasfh\n";
	vt[0] = vt[n];
	vt[n+1] = vt[1];
	for(int i = 1 ; i <= n ; i ++){
		if(vt[i] == 1 && vt[i-1] ==0){
			l = i;
		}
		if(vt[i] == 1 && vt[i+1] ==0){
			r = i;
		}
	}
	int sum = 0  , da= 0;
	if(l <= r){
		if(r-l +1 >= 2){
			for(int i = l ; i < r ;i ++){
				sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
			}
			sum += ds[r].x*ds[l].y - ds[l].x*ds[r].y;
			if(r-l+1 >= 3){
				da = max(da , sum);
			}
		} 
	}else{
		if(r + n-l +1 >= 2){
			for(int i = 1 ; i < r ; i ++){
				sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
			}
			sum += ds[r].x*ds[l].y - ds[l].x*ds[r].y;
			for(int i = l ; i < n ; i++){
				sum += ds[i].x*ds[i+1].y - ds[i+1].x*ds[i].y;
			}
			sum += ds[n].x*ds[1].y - ds[1].x*ds[n].y;
			if(r + n - l + 1 >= 3) da = max(da , sum);
		}
	}
	
	A.push_back(A[1]);
	for(int i = 1 ; i < A.size()-1 ; i ++){
		int x = A[i].x;
		int y = A[i].y;
		int u = A[i+1].x;
		int v = A[i+1].y;
		
		while(!tes(x , y , u , v , ds[l].x , ds[l].y)){
			
			while(tet(ds[l].x , ds[l].y , ds[r].x , ds[r].y , x , y) ){
				
				if(siz(l , r) >= 3){
					da = max(da , sum);
				}

				if( !tes(x , y , u , v , ds[r].x , ds[r].y) || tes(x , y , u , v , ds[tren(r)].x , ds[tren(r)].y))
					tang(l , r , sum);
				else break;
			}
			giam(l , r , sum);
		}
		
		
		while(!tes(x , y , u , v , ds[r].x , ds[r].y) || tes(x , y , u , v , ds[tren(r)].x , ds[tren(r)].y)){
			tang(l , r , sum);
		}
		
		if(siz(l , r) >= 3){
			da = max(da , sum);
//			cout <<sum <<endl;
		}
		
	}
	cout <<da;
	
	
	
}

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:192:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<op>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |  for(int i = 1 ; i < A.size()-1 ; i ++){
      |                  ~~^~~~~~~~~~~~

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