結果

問題 No.180 美しいWhitespace (2)
ユーザー ttkkggww
提出日時 2022-08-21 20:00:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,820 ms / 5,000 ms
コード長 909 bytes
コンパイル時間 4,462 ms
コンパイル使用メモリ 254,884 KB
最終ジャッジ日時 2025-01-31 02:35:44
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<ll,ll>;
vector<ll> a,b;
vector<P> ab;
ll n;

ll f(ll x){
	if(x<1)return 1e15;
	ll mx = a[0]+b[0]*x;;
	ll mn = a[0]+b[0]*x;;
	for(ll i = 0; i<n;i++){
		mx = max(mx,a[i]+b[i]*x);
		mn = min(mn,a[i]+b[i]*x);
	}
	return mx - mn;
}


void solve(){
	P ans(f(1),1);
	for(ll i = 0;i<n;i++){
		for(ll j = i+1;j<n;j++){
			//y = ai + bix
			//y = aj + bjx
			//0 = (ai-aj) + (bi-bj)x
			//x = (aj-ai)/(bi-bj)
			if(b[i]==b[j])continue;
			ll x = (a[j]-a[i])/(b[i]-b[j]);
			ans = min(ans,P(f(x),x));
			x++;
			ans = min(ans,P(f(x),x));
			x--;
			x--;
			ans = min(ans,P(f(x),x));
		}
	}
	cerr<<f(2)<<endl;
	cout<<ans.second<<endl;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n;
	a = b = vector<ll>(n);
	for(int i =0;i<n;i++)cin >> a[i] >> b[i];
	solve();
}
0