Submission #932097

#	Time	Username	Problem	Language	Result	Execution time	Memory
932097		vjudge1	SIR (COI15_sir)	C++17	0 / 100	124 ms	16140 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 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) ? 1 : 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(){

	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});
	}
	
	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]);
			}
		}
	}int P = a.size();
	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 ;
//	for(int i = 0 ; i < A.size()-1 ; i++) cout << A[i].x <<" " << A[i].y << '\n';
	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) ;
	}
	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);
		}
	}
	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[tren(r)].x , ds[tren(r)].y)){
			tang(l , r , sum);
		}
		while(!tes(x , y , u , v , ds[l].x , ds[l].y)){
			giam(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:152:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<op>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int i = 1 ; i < A.size()-1 ; i ++){
      |                  ~~^~~~~~~~~~~~
sir.cpp:91:7: warning: unused variable 'P' [-Wunused-variable]
   91 |  }int P = a.size();
      |       ^

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