Submission #72686

#	Time	Username	Problem	Language	Result	Execution time	Memory
72686		gs14004	Hill Reconstruction (FXCUP3_hill)	C++17	100 / 100	523 ms	61036 KiB

hill

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 300050;
 
int n; lint c;
pi den, a[MAXN];
vector<pi> stk;
 
lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
 
bool big_giulgi(pi a, pi b, llf c){
	return (b.second - a.second) > (b.first - a.first) * c;
}
 
lint trial(llf x){
	stk.clear();
	stk.push_back(a[0]);
	lint ans = 0;
	for(int i=1; i<n; i++){
		while(stk.size() >= 2 && big_giulgi(stk.back(), a[i], x)){
			ans += ccw(stk[stk.size()-2], stk.back(), a[i]);
			stk.pop_back();
		}
		if(big_giulgi(stk.back(), a[i], x)){
			return 3e18;
		}
		stk.push_back(a[i]);
	}
	return ans;
}
 
bool cmp(pi a, pi b){
	return 1ll * a.first * b.second < 1ll * b.first * a.second;
}
 
int gcd(int x, int y){ return y ? gcd(y, x%y) : x; }
 
int main(){
	scanf("%d %lld",&n,&c);
	c <<= 1;
	for(int i=0; i<n; i++) scanf("%d",&a[i].first);
	for(int i=0; i<n; i++) scanf("%d",&a[i].second);
	long double s = 0, e = 2e9;
	for(int i=0; i<100; i++){
		long double m = (s+e)/2;
		if(trial(m) <= c) e = m;
		else s = m;
	}
	assert(trial(e) <= c);
	pi ans(0, 1);
	for(int i=1; i<stk.size(); i++){
		ans = max(ans, pi(stk[i].second - stk[i-1].second, stk[i].first - stk[i-1].first), cmp); 
	}
	int g = gcd(ans.first, ans.second);
	ans.first /= g;
	ans.second /= g;
	printf("%d/%d\n", ans.first, ans.second);
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<stk.size(); i++){
               ~^~~~~~~~~~~
hill.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&c);
  ~~~~~^~~~~~~~~~~~~~~~~
hill.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].first);
                         ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].second);
                         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 68 / 68