URAL1062[Triathlon]

半平面交，然后先暂时用O(n^2)的过了。

半平面交O(n^2)，一共这样做n次，总的时间复杂度O(n^3)。

半平面交有O(nlogn)的分治法，不过现在还不会。

然后讲一下O(n^2)的半平面交：

先有一个凸包{(-oo,-oo),(oo,-oo),(oo,oo),(-oo,oo)}（点有序），然后用线依次去切。

对凸包上的点：

1.如果它不被切掉，保留它(如下图中的绿线切C点)；

2.它被切掉，先丢掉它（如下图中的红线切A点），然后如果与它相邻的点不被切掉（相邻指按级角排序后的顺序中相邻），那么加入它与相邻点所在直线与切割线的交点（如下图中的蓝线切B点，加入的是两个红点）。

主要思路就是这样了。

CODE:

//DATE:2010-4-1

#include <cstdio>

using std::printf;

using std::scanf;

#include <cstring>

using std::memcpy;

 

#define MAXN 100

#define KIND 3

#define oo 1e10

#define zero 1e-10

 

typedef int Player[MAXN][KIND];

struct Point{double x,y;};

struct Line{double a,b,c;};

 

int N;

Player player;

Line line[MAXN];

bool canWin[MAXN];

 

void read()

{

     scanf(“%d”,&N);

     for (int i=0;i<N;i++)

         for (int j=0;j<KIND;j++)

             scanf(“%d”,&player[i][j]);

}

void write()

{

     for (int i=0;i<N;i++)

         if (canWin[i]) printf(“Yes\n”);

         else printf(“No\n”);

}

void initLines()

{

     for (int i=0;i<N;i++)

         line[i].a=1.0/player[i][0],

         line[i].b=1.0/player[i][1],

         line[i].c=1.0/player[i][2];

}

Point intersect(Line l,Point a,Point b)

{

      Point get;

      double fa=l.a*a.x+l.b*a.y+l.c;

      double fb=l.a*b.x+l.b*b.y+l.c;

      get.x=(fb*a.x-fa*b.x)/(fb-fa);

      get.y=(fb*a.y-fa*b.y)/(fb-fa);

      return get;

}

void cut(Point* p,int& pn,Line cutter)

{

     Point q[MAXN+4];

     int qn=0;

     for (int i=0;i<pn;i++)

     {

         if (p[i].x*cutter.a+p[i].y*cutter.b+cutter.c>zero)

            q[qn++]=p[i];

         else

         {

             int before=(i-1+pn)%pn;

             int next=(i+1)%pn;

             if (p[before].x*cutter.a+p[before].y*cutter.b+cutter.c>zero)

                q[qn++]=intersect(cutter,p[before],p[i]);

             if (p[next].x*cutter.a+p[next].y*cutter.b+cutter.c>zero)

                q[qn++]=intersect(cutter,p[i],p[next]);

         }

     }

     memcpy(p,q,sizeof(q));

     pn=qn;

}

bool isEmpty(Line* l,int n)

{

     Point p[MAXN+4];

     int pn=0;

     p[pn].x=0;

     p[pn].y=0;

     pn++;

     p[pn].x=oo;

     p[pn].y=0;

     pn++;

     p[pn].x=oo;

     p[pn].y=oo;

     pn++;

     p[pn].x=0;

     p[pn].y=oo;

     pn++;

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

         cut(p,pn,l[i]);

     return pn<3;

    

}

bool can(int id)

{

     Line l[MAXN];

     memcpy(l,line,sizeof(line));

     for (int i=0;i<N;i++)

         if (i!=id)

            l[i].a-=l[id].a,

            l[i].b-=l[id].b,

            l[i].c-=l[id].c;

     l[id]=l[N-1];

     if (isEmpty(l,N-1)) return false;

     else return true;

}

void solve()

{

     initLines();

     for (int i=0;i<N;i++)

         canWin[i]=can(i);

}

int main()

{

    read();

    solve();

    write();

    return 0;

}