LA 2218 (半平面交) Triathlon

时间：2022-01-14 03:51:15

题意：

有n个选手，铁人三项有连续的三段，对于每段场地选手i分别以vi, ui 和 wi匀速通过。

对于每个选手，问能否通过调整每种赛道的长度使得他成为冠军(不能并列)。

分析：

粗一看，这不像一道计算几何的题目。

假设赛道总长度是1，第一段长x，第二段长y，第三段则是1-x-y

那么可以计算出每个选手完成比赛的时间Ti

对于选手i，若要成为冠军则有Ti < Tj (i ≠ j)

于是就有n-1个不等式，每个不等式都代表一个半平面。

在加上x>0, y>0, 1-x-y>0 这三个半平面一共有n+2个半平面。如果这些半平面交非空，则选手i可以成为冠军。

最终，还是转化成了半平面交的问题。

细节：

  • 对于半平面 ax+by+c > 0 所对应的向量(b, -a)是和系数的正负没有关系的，可以自己试验下。开始我纠结了好长时间
  • if(fabs(a) > fabs(b))    P = Point(-c/a, )
    
else P = Point(, -c/b);

    对于这段代码不是太清楚它的含义，因为不管怎样P都是在ax+by+c = 0 这条直线上的。我猜可能是减小浮点运算的误差吧？

 //#define LOCAL

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 using namespace std;

 const double eps = 1e-;

 const int maxn =  + ;

 int v[maxn], u[maxn], w[maxn];

 struct Point

 {

     double x, y;

     Point(double x=, double y=):x(x), y(y) {}

 };

 typedef Point Vector;

 Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); }

 Point operator - (Point a, Point b) { return Point(a.x-b.x, a.y-b.y); }

 Vector operator * (Vector a, double p) { return Vector(a.x*p, a.y*p); }

 Vector operator / (Vector a, double p) { return Vector(a.x/p, a.y/p); }

 bool operator < (const Point& a, const Point& b)

 { return a.x < b.x || (a.x == b.x && a.y < b.y); }

 bool operator == (const Point& a, const Point& b)

 { return a.x == b.x && a.y == b.y; }

 double Dot(const Vector& a, const Vector& b) { return a.x*b.x + a.y*b.y; }

 double Cross(const Vector& a, const Vector& b) { return a.x*b.y - a.y*b.x; }

 double Length(const Vector& a) { return sqrt(Dot(a, a)); }

 Vector Normal(const Vector& a)

 {

     double l = Length(a);

     return Vector(-a.y/l, a.x);

 }

 double PolygonArea(const vector<Point>& p)

 {

     int n = p.size();

     double ans = 0.0;

     for(int i = ; i < n-; ++i)

         ans += Cross(p[i]-p[], p[i+]-p[]);

     return ans/;

 }

 struct Line

 {

     Point P;

     Vector v;

     double ang;

     Line() {}

     Line(Point p, Vector v):P(p), v(v) { ang = atan2(v.y, v.x); }

     bool operator < (const Line& L) const

     {

         return ang < L.ang;

     }

 };

 bool OnLeft(const Line& L, Point p)

 {

     return Cross(L.v, p-L.P) > ;

 }

 Point GetLineIntersevtion(const Line& a, const Line& b)

 {

     Vector u = a.P - b.P;

     double t = Cross(b.v, u) / Cross(a.v, b.v);

     return a.P + a.v*t;

 }

 vector<Point> HalfplaneIntersection(vector<Line> L)

 {

     int n = L.size();

     sort(L.begin(), L.end());

     int first, last;

     vector<Point> p(n);

     vector<Line> q(n);

     vector<Point> ans;

     q[first=last=] = L[];

     for(int i = ; i < n; ++i)

     {

         while(first < last && !OnLeft(L[i], p[last-])) last--;

         while(first < last && !OnLeft(L[i], p[first])) first++;

         q[++last] = L[i];

         if(fabs(Cross(q[last].v, q[last-].v)) < eps)

         {

             last--;

             if(OnLeft(q[last], L[i].P)) q[last] = L[i];

         }

         if(first < last) p[last-] = GetLineIntersevtion(q[last-], q[last]);

     }

     while(first < last && !OnLeft(q[first], p[last-])) last--;

     if(last - first <= )    return ans;

     p[last] = GetLineIntersevtion(q[first], q[last]);

     for(int i = first; i <= last; ++i)    ans.push_back(p[i]);

     return ans;

 }

 int main(void)

 {

     #ifdef    LOCAL

         freopen("2218in.txt", "r", stdin);

     #endif

     int n;

     while(scanf("%d", &n) ==  && n)

     {

         for(int i = ; i < n; ++i) scanf("%d%d%d", &v[i], &u[i], &w[i]);

         for(int i = ; i < n; ++i)

         {

             int ok = ;

             double k = ;

             vector<Line> L;

             for(int j = ; j < n; ++j) if(j != i)

             {

                 if(v[i]<=v[j] && u[i]<=u[j] && w[i]<=w[j]) { ok = ; break; }

                 if(v[i]>v[j] && u[i]>u[j] && w[i]>w[j]) continue;

                 double a = (k/v[j]-k/v[i]+k/w[i]-k/w[j]);

                 double b = (k/u[j]-k/u[i]+k/w[i]-k/w[j]);

                 double c = k/w[j]-k/w[i];

                 //L.push_back(Line(Point(0, -c/b), Vector(b, -a)));

                 Point P;

                 Vector V(b, -a);

                 if(fabs(a) > fabs(b))    P = Point(-c/a, );

                 else P = Point(, -c/b);

                 L.push_back(Line(P, V));

             }

             if(ok)

             {

                 L.push_back(Line(Point(, ), Vector(, -)));

                 L.push_back(Line(Point(, ), Vector(, )));

                 L.push_back(Line(Point(, ), Vector(-, )));

                 vector<Point> Poly = HalfplaneIntersection(L);

                 if(Poly.empty()) ok = ;

             }

             if(ok) puts("Yes"); else puts("No");

         }

     }

     return ;

 }

代码君

相关文章