Submission #665946


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;

int N, x[1000], y[1000], c[1000];
double ret = 1e9;

double e(double row, double col)
{
  double cost = 0;
  for(int i = 0; i < N; i++) {
    cost = max(cost, max(fabs(x[i] - row), fabs(y[i] - col)) * c[i]);
  }
  return(cost);
}

double f(double value)
{
  double res = 1e9;
  double left = -1e5, right = 1e5;
  for (int loop = 0; loop < 100; ++loop){
    double a = e(value, (left * 2 + right) / 3);
    double b = e(value, (left + right * 2) / 3);
    res = min(res, a);
    res = min(res, b);
    if (a < b){
      right = (left + right * 2) / 3;
    } else {
      left = (left * 2 + right) / 3;
    }
  }
  return(res); 
}

double search()
{
  double left = -1e5, right = 1e5;
  for (int loop = 0; loop < 100; ++loop){
    double a = f((left * 2 + right) / 3);
    double b = f((left + right * 2) / 3);
    ret = min(a, ret);
    ret = min(b, ret);
    if (a < b) {
      right = (left + right * 2) / 3;
    } else {
      left = (left * 2 + right) / 3;
    }
  }
  return (right + left) * 0.5;
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> x[i] >> y[i] >> c[i];
  }
  cout << e(5, 5) << endl;

  search();
  cout << fixed << setprecision(10) << ret << endl;
}

Submission Info

Submission Time
Task B - 高橋ノルム君
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1350 Byte
Status
Exec Time 227 ms
Memory 256 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
Subtask1 0 / 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 0 / 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
Case Name Status Exec Time Memory
subtask0_sample_01.txt 5 ms 256 KB
subtask0_sample_02.txt 5 ms 256 KB
subtask0_sample_03.txt 6 ms 256 KB
subtask0_sample_04.txt 6 ms 256 KB
subtask1_01.txt 5 ms 256 KB
subtask1_02.txt 5 ms 256 KB
subtask1_03.txt 5 ms 256 KB
subtask1_04.txt 165 ms 256 KB
subtask1_05.txt 163 ms 256 KB
subtask1_06.txt 164 ms 256 KB
subtask1_07.txt 165 ms 256 KB
subtask1_08.txt 165 ms 256 KB
subtask1_09.txt 164 ms 256 KB
subtask1_10.txt 163 ms 256 KB
subtask1_11.txt 163 ms 256 KB
subtask1_12.txt 227 ms 256 KB
subtask1_13.txt 164 ms 256 KB
subtask2_01.txt 5 ms 256 KB
subtask2_02.txt 5 ms 256 KB
subtask2_03.txt 5 ms 256 KB
subtask2_04.txt 164 ms 256 KB
subtask2_05.txt 164 ms 256 KB
subtask2_06.txt 163 ms 256 KB
subtask2_07.txt 164 ms 256 KB
subtask2_08.txt 165 ms 256 KB
subtask2_09.txt 164 ms 256 KB
subtask2_10.txt 164 ms 256 KB
subtask2_11.txt 163 ms 256 KB
subtask2_12.txt 163 ms 256 KB
subtask2_13.txt 164 ms 256 KB