AtCoder Regular Contest 049

Submission #666159

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
const ll eps=1e-9;
vector<pair<ll,ll> > makes(ll med,ll x,ll y,ll c){
	vector<pair<ll,ll> > point;
	point.push_back(make_pair(x-med/c,y+med/c));//左上
	point.push_back(make_pair(x+med/c,y+med/c));//右上
	point.push_back(make_pair(x-med/c,y-med/c));//左下
	point.push_back(make_pair(x+med/c,y-med/c));//右下
	return point;
}
int main(){
	ll n;	cin>>n;
	vector<ll> x(n),y(n),c(n);
	for(int i=0;i<n;i++)	cin>>x[i]>>y[i]>>c[i];
	ll left=0,right=1e9;
	for(int t=0;t<100;t++){
		ll med=(left+right)/2;//行ける秒数
		vector<pair<ll,ll> > point=makes(med,x[0],y[0],c[0]);
		bool failed=false;
		for(int i=1;i<n;i++){
			vector<pair<ll,ll> > p=makes(med,x[i],y[i],c[i]);
			//範囲よりも左にある
			if(point[0].first-p[3].first>-eps)	failed=true;
			//上にある
			else if(p[3].second-point[0].second>-eps)	failed=true;
			//右
			else if(p[0].first-point[3].first>-eps)	failed=true;
			//下
			else if(point[3].second-p[0].second>-eps)	failed=true;
			if(failed)	break;
			if(p[0].first-point[0].first>-eps){//左の確認
				point[0].first=p[0].first;
				point[2].first=p[2].first;
			}
			if(point[0].second-p[0].second>-eps){//上
				point[0].second=p[0].second;
				point[1].second=p[0].second;
			}
			if(point[3].first-p[3].first>-eps){//右
				point[3].first=p[3].first;
				point[1].first=p[1].first;
			}
			if(p[3].second-point[3].second>-eps){//下
				point[3].second=p[3].second;
				point[2].second=p[2].second;
			}
		}
		if(failed)	left=med;
		else right=med;
	}
	printf("%.15Lf",left);
	return 0;
}

Submission

Task問題 B - 高橋ノルム君
User nameユーザ名 fiord
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1663 Byte
File nameファイル名
Exec time実行時間 49 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample -
Subtask1 30 / 30 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt
Subtask2 70 / 70 subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt AC 4 ms 256 KB
subtask0_sample_02.txt AC 4 ms 256 KB
subtask0_sample_03.txt AC 4 ms 256 KB
subtask0_sample_04.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 4 ms 256 KB
subtask1_04.txt AC 39 ms 256 KB
subtask1_05.txt AC 48 ms 256 KB
subtask1_06.txt AC 43 ms 256 KB
subtask1_07.txt AC 43 ms 256 KB
subtask1_08.txt AC 41 ms 256 KB
subtask1_09.txt AC 46 ms 256 KB
subtask1_10.txt AC 39 ms 256 KB
subtask1_11.txt AC 48 ms 256 KB
subtask1_12.txt AC 41 ms 256 KB
subtask1_13.txt AC 46 ms 256 KB
subtask2_01.txt AC 4 ms 256 KB
subtask2_02.txt AC 4 ms 256 KB
subtask2_03.txt AC 4 ms 256 KB
subtask2_04.txt AC 47 ms 256 KB
subtask2_05.txt AC 49 ms 256 KB
subtask2_06.txt AC 42 ms 256 KB
subtask2_07.txt AC 26 ms 256 KB
subtask2_08.txt AC 41 ms 256 KB
subtask2_09.txt AC 44 ms 256 KB
subtask2_10.txt AC 46 ms 256 KB
subtask2_11.txt AC 48 ms 256 KB
subtask2_12.txt AC 38 ms 256 KB
subtask2_13.txt AC 47 ms 256 KB