제출 #158685

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

sir

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

const int maxn=3e5+5;

pair < ll, ll > l[maxn];
pair < ll, ll > svi[maxn];
vector < pair < ll, ll > > bitne;
vector < pair < ll, ll > > ost;

ll hull(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);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> l[i].first >> l[i].second;
	}
	int m;
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> svi[i].first >> svi[i].second;
	}
	sort(svi, svi+m);
	for(int i=0; i<m; i++){
		while(bitne.size()>1 && hull(bitne[bitne.size()-2], bitne.back(), svi[i])<=0){
			bitne.pop_back();
		}
		bitne.push_back(svi[i]);
	}
	for(int i=m-1; i>-1; i--){
		while(ost.size()>1 && hull(ost[ost.size()-2], ost.back(), svi[i])<=0){
			ost.pop_back();
		}
		ost.push_back(svi[i]);
	}
	for(int i=ost.size()-2; i>0; i--){
		bitne.push_back(ost[i]);
	}
	int sz=bitne.size();
	int pos1, pos2=0;
	ll mini=1e10;
	for(int i=0; i<sz; i++){
		if(mini>abs(l[0].first-bitne[i].first)+abs(l[0].second-bitne[i].second)){
			mini=abs(l[0].first-bitne[i].first)+abs(l[0].second-bitne[i].second);
			pos1=i;
		}
	}
	ll sum=0;
	ll maksi=0;
	int pos3;
	for(int i=0; i<n; i++){
		while(hull(l[i], bitne[(pos1+1)%sz], bitne[pos1])>0){
			pos1=(pos1+1)%sz;
		}
		while(hull(l[i], l[(pos2+1)%n], bitne[pos1])>0){
			sum+=hull(l[i], l[pos2], l[(pos2+1)%n]);
			pos2=(pos2+1)%n;
		}
		pos3=(i+1)%n;
		maksi=max(maksi, sum);
		sum-=hull(l[i], l[pos3], l[pos2]);
	}
	cout << maksi << '\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sir.cpp: In function 'int main()':
sir.cpp:51:6: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int pos1, pos2=0;
      ^~~~

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