CF73F-Plane-of-Tanks

一眼二分题，check打懵逼 ——某奆佬

好吧，，，在这题中，如果$v_1 \le v_2$且$v_1$为可行解，则$v_2$必然为可行解，所以是有单调性的，所以可以二分，然后二分的check就不会打了。。

---

重点：关于check

1. 分析

   分析一下，发现我们其实可以假设所有坦克都转向B点（因为如果一个坦克能在Pedalny行驶过程中（包括AB）指向Pedalny，必然能在Pedalny到达B点之前指向B点，于是只要等Pedalny来了之后一起轰击就行了），于是我们只需要计算出Pedalny到达B点之前，有多少坦克能指向B点就行了。为了让更多的坦克指向B点（误，我们需要计算出对于每个坦克，是顺时针旋转指向B点，还是逆时针旋转指向B点快。

2. 计算旋转时间

   然后我们发现每个坦克的旋转速度是确定的，于是我们只需要计算旋转角就行了，然后就变成了用勾股定理求出边长，然后使用求直角三角形的角的正切值之后$tan^{-1}$算出角度，然后就解决问题了。

   如图，CD//x轴，坦克C初始面向射线CE方向，BF$\perp$CD，题目给出了$\angle DCF$，我们只需要计算$\angle BCF$即可，具体计算为:$\angle BCF=tan^{-1}(\frac {BF} {CF})$,最终旋转角为$\angle DCF + \angle BCF$

   

似乎比官方题解简单多了。。个人写实数二分较为奇怪，请勉强接受一下

#include <bits/stdc++.h>
#define EPS 1e-6
#define PI acos(-1)
using namespace std;

typedef long long ll;

int n, m, k;

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) : x(x), y(y) {}
  double abs() const { return hypot(x, y); }
  double arg() const { return atan2(y, x); }
  Point operator*(double o) const { return Point(x * o, y * o); }
  Point operator+(const Point &o) const { return Point(x + o.x, y + o.y); }
  Point operator-(const Point &o) const { return Point(x - o.x, y - o.y); }
  bool operator<(const Point &o) const {
    return x < o.x - EPS || (x < o.x + EPS && y < o.y - EPS);
  }
};

Point A, B;
map<double, int> js;

int main() {
  scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y);
  scanf("%d", &n);
  double x, y, a, w;
  for (int i = 0; i < n; i++) {
    scanf("%lf%lf%lf%lf", &x, &y, &a, &w);
    if (abs(w) < EPS)
      continue;
    Point p = {x, y};
    double v = -2;
    for (int j = 0; j <= 100; j++) {
      Point tp = (B - A) * (j / 100.0) + A;
      double arg = (tp - p).arg() - a;
      if (arg > 2 * PI)
        arg -= 2 * PI;
      while (arg < 0)
        arg += 2 * PI;
      if (arg > 2 * PI - arg)
        arg = 2 * PI - arg;
      double t = arg / w;
      v = v < -1 ? (tp - A).abs() / t : max(v, (tp - A).abs() / t);
    }
    js[v]++;
  }
  scanf("%d", &k);
  int sk = 0;
  double t = -10;
  for (map<double, int>::reverse_iterator it = js.rbegin(); it != js.rend();
       it++) {
    if (sk + it->second > k) {
      t = it->first;
      break;
    }
    sk += it->second;
  }
  printf("%.4lf\n", t < -1 ? 0 : t);
  return 0;
}