破阵子（三分+凸包旋转卡壳）

本文主要是介绍破阵子（三分+凸包旋转卡壳），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

平面上有n个点，每个点有各自的速度向量，现在给出0时刻，在同一时刻，平面点的最远距离叫做special dis
他们每个点的位置和每个点的速度向量，现在求在哪个时刻的时候，他们的special dis 最小，并输出这个距离。

Input

输入一个正整数T(T<=10),表示有T组数据，每组数据包括一个n(n<=10000),表示有n个点，每行包括每个点的坐标 (x,y) (-100000<=x,y<=100000)，速度向量 (vx,vy)  (-1000<=vx,vy<=1000)

Output

输出在哪个时刻的时候,special dis距离最小，保留两位小数

Sample Input

2
2
0 0 1 0
2 0 -1 0
4
27 27 0 2
58 88 -8 -1
-22 7 1 -1
-38 -26 5 9

Sample Output

1.00 0.00
8.89 81.00

思路：

求最大值中最小值，首先想到二分

但发现dis不一定随时间增大而增大，

事实上，两点间距离，要么直接增加，要么先减少再增加。

所以dis也是要么直接增加，要么先减少再增加。

这是一个单峰的变化。

用到三分；

其次，对于每个时间点，我们可以知道每个点坐标。

多对点的最远距离一定是在凸包上取得的（证明可以搜搜）

找到凸包之后，用旋转卡壳求取一个时间点的最远距离；

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
#define per(i,a,b) for(int i=a;i<=b;i++)
#define ber(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e4 + 5;
const LL mod = 10000000033;
double eps = 1e-8;
int top = 0, n;
struct Point
{
   double x;
   double y;
   double vx;
   double vy;
}p[N], tmp[N], s[N];
bool cmp(struct Point a, struct Point b)
{
   if (a.x != b.x)
       return a.x < b.x;
   return a.y < b.y;
}
void into(double t)
{
   per(i, 1, n)
   {
       tmp[i].x = p[i].x + p[i].vx * t;
       tmp[i].y = p[i].y + p[i].vy * t;
   }
   sort(tmp + 1, tmp + 1 + n, cmp);
}
double cross(struct Point& a, struct Point& b, struct Point& c)
{
   return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void Andro(double t)
{
   top = -1;
   into(t);
   per(i, 1, n)
   {
       while (top > 0 && cross(s[top - 1], s[top], tmp[i]) <= 0) top--;
       s[++top] = tmp[i];
   }
   int tt = top;
   ber(i, n - 1, 1)
   {
       while (top > tt && cross(s[top - 1], s[top], tmp[i]) <= 0) top--;
       s[++top] = tmp[i];
   }
}
double dis(struct Point& a, struct Point& b)
{
   return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double f(double t)
{
   Andro(t);
   if (top <= 2)
       return dis(s[0], s[1]);
   double ans = 0;
   for (int i = 0, j = 2; i < top; i++)
   {
       while (abs(cross(s[i], s[i + 1], s[j])) < abs(cross(s[i], s[i + 1], s[j + 1]))) j = (j + 1) % top;
       ans = max(ans, max(dis(s[i], s[j]), dis(s[i + 1], s[j])));
   }
   return ans;
}
double sanfen(double l, double r)
{
   double mi, ma;
   while (r - l > eps)
   {
       mi = l + (r - l) / 3;
       ma = r - (r - l) / 3;
       if (f(mi) >= f(ma)) l = mi;
       else r = ma;
   }
   return mi;
}
int main()
{
   int T;
   cin >> T;
   while (T--)
   {
       cin >> n;
       per(i, 1, n)
           cin >> p[i].x >> p[i].y >> p[i].vx >> p[i].vy;
       double t = sanfen(0, 10000);
       printf("%.2f %.2f\n", t, f(t));
   }
   return 0;
}