結果

問題 No.180 美しいWhitespace (2)
ユーザー Tawara
提出日時 2015-08-26 21:19:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,493 bytes
コンパイル時間 505 ms
コンパイル使用メモリ 73,656 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-18 14:44:37
合計ジャッジ時間 11,233 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;
typedef vector <string> VS;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, LL> PIL;
typedef vector <PIL> VPIL;


#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define sort(c) sort((c).begin(),(c).end())

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)

#define MAX_INT 2147483647
#define MAX_F 1000000000000

pair <LL,LL> func(LL x, LL tmp_x, LL f_x, int a[], int b[], int N){
	LL max_f = 0, min_f = MAX_F, f_tmpx;
	rep(i,N){
		f_tmpx = a[i]+b[i]*tmp_x;
		max_f = max(max_f, f_tmpx);
		min_f = min(min_f, f_tmpx);
	}
	f_tmpx = max_f - min_f;
	if(f_tmpx < f_x || (f_tmpx == f_x && tmp_x < x))
		return pair <LL,LL> (tmp_x,f_tmpx);
	else
		return pair <LL,LL> (x,f_x);
}
int main(){
	int N;
	pair <LL,LL> res;
	LL tmp_x;
	cin >> N;
	int a[N], b[N];
	rep(i,N){cin >> a[i] >> b[i];}
	res = func(1,1,MAX_F,a,b,N);
	rep(i,N-1)
		range(j,i+1,N){
			if(b[i]==b[j]) continue;
			tmp_x = - (a[i] - a[j])/(b[i]-b[j]);
			if (tmp_x < 1) continue;
			res = func(res.first,tmp_x,res.second,a,b,N);
			if (abs(a[i] - a[j])%abs(b[i]-b[j]) > 0){
				res = func(res.first,tmp_x+1,res.second,a,b,N);
			}
		}
	cout << res.first << endl;
	return 0;
}
0