sgu401.cpp

SGU题库第四版前10题的题目解答。前三题是CPP程序

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const double eps = 1e-10;
const int maxn = 100000;

inline int Sign(double a) {
  return a < -eps ? -1 : a > eps;
}

inline double Sqr(double a) {
  return a * a;
}

inline double Sqrt(double a) {
  return a <= 0 ? 0 : sqrt(a);
}

double width[maxn], velocity[maxn];
double need[maxn], own[maxn];
double u, t;
int n;

void Init() {
  int i;
  for (i = 0; i < n; i++)
    scanf("%lf %lf", &width[i], &velocity[i]);
}

inline double Calc(int i, double own) {
  return Sqrt(Sqr(u * own) - Sqr(width[i])) + velocity[i] * own;
}

bool Exchange(int a, int b) {
  double lower = need[a];
  double upper = own[a] + own[b] - need[b];
  double curr = own[a], prev;
  double step = upper - lower;
  double x, temp, value = Calc(a, own[a]) + Calc(b, own[b]);
  int i;
  bool res = 0;
  for (; Sign(step); step /= 2) {
    prev = curr;
    for (i = -1; i <= 1; i++) {
      x = prev + step * i;
      if (x < lower) x = lower;
      if (x > upper) x = upper;
      temp = Calc(a, x) + Calc(b, own[a] + own[b] - x);
      if (Sign(temp - value) > 0) {
        res = 1;
        curr = x;
        value = temp;
      }
    }
  }
  own[b] = own[a] + own[b] - curr;
  own[a] = curr;
  return res;
}

void Work() {
  int i, j;
  double sum = 0, ll = 0;
  for (i = 0; i < n; i++)
    sum += need[i] = width[i] / u;
  if (Sign(sum - t) > 0) {
    printf("-1\n");
    return;
  }
  for (i = 0; i < n; i++)
    own[i] = need[i] + (t - sum) / n;
  bool flag = 1;
  while (flag) {
    flag = 0;
    for (i = 0; i + 1 < n; i++)
      for (j = i + 1; j < n; j++)
        if (Exchange(i, j)) flag = 1;
  }
  sum = 0;
  for (i = 0; i < n; i++) {
    sum += Calc(i, own[i]);
    ll += width[i];
  }
  printf("%.10lf\n", Sqrt(Sqr(sum) + Sqr(ll)));
  for (i = 0; i < n; i++) {
    if (i) printf(" ");
    printf("%.10lf", own[i]);
  }
  printf("\n");
}

int main() {
  while (scanf("%d %lf %lf", &n, &u, &t) == 3) {
    Init();
    Work();
  }
  return 0;
}