oj.uz

답안 #158741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158741 2019-10-18T15:00:14 Z vanic SIR (COI15_sir) C++14
100 / 100
 223 ms 20064 KB 
#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(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%lld%lld", &l[i].first, &l[i].second);
	}
	int m;
	scanf("%d", &m);
	for(int i=0; i<m; i++){
		scanf("%lld%lld", &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=1; i<ost.size()-1; i++){
		bitne.push_back(ost[i]);
	}
	int sz=bitne.size();
/*	printf("%d\n", sz);
	for(int i=0; i<sz; i++){
		printf("%lld %lld\n", bitne[i].first, bitne[i].second);
	}*/
	int pos1=0, 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]);
	}
	printf("%lld\n", maksi);
	return 0;
}

Compilation message

sir.cpp: In function 'int main()':
sir.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<ost.size()-1; i++){
               ~^~~~~~~~~~~~~
sir.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &l[i].first, &l[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &svi[i].first, &svi[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 4 ms 504 KB Output is correct

Subtask #3
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 10864 KB Output is correct
2 Correct 215 ms 18728 KB Output is correct
3 Correct 185 ms 20064 KB Output is correct
4 Correct 58 ms 5752 KB Output is correct
5 Correct 172 ms 16844 KB Output is correct
6 Correct 171 ms 14712 KB Output is correct