Submission #158741

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158741	2019-10-18T15:00:14 Z	vanic	SIR (COI15_sir)	C++14	100 / 100	223 ms	20064 KB

sir

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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