Skip to content

Instantly share code, notes, and snippets.

@dcrystalj
Last active August 29, 2015 14:16
Show Gist options
  • Save dcrystalj/18c9b952ea199ed2327c to your computer and use it in GitHub Desktop.
Save dcrystalj/18c9b952ea199ed2327c to your computer and use it in GitHub Desktop.
time-limit
#include <stdio.h>
#include <float.h>
using namespace std;
bool isUpper(double t, int[] s, int[] v) {
double m = FLT_MIN;
for (int i = 0; i < n; ++i)
{
if (v[i] < 0)
{
if (s[i] + v[i] * t <= m)
return true;
}
else
m = max(m, s[i] + v[i] * t);
}
return false;
}
int main()
{
int n;
scanf("%d", &n);
int v [n];
int s [n];
double l = 0;
double h = 10000000000;
double m;
bool isNegative;
bool isPositive;
for (int i = 0; i < n; ++i)
{
scanf("%d %d", &s[i], &v[i]);
if (v[i] > 0)
isPositive = true;
if (v[i] < 0 && isPositive)
isNegative = true;
}
if ( !isNegative )
{
printf("-1.0000000000");
return 0;
}
while (fabs(h-l) > 0.0000000001)
{
m = (h-l) / 2.0;
if ( isUpper(m, s, v) )
h = m;
else
l = m;
}
printf("%.10f", minimum);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment