设为首页 加入收藏

TOP

URAL 1062 - Triathlon(半平面交)
2014-11-23 21:46:39 来源: 作者: 【 】 浏览:11
Tags:URAL 1062 Triathlon 面交

这个题乍眼一看好像很简单,然后我就认为u、v、w只要有全部比另外一个人小的就不能win,否则就能win,但是这个思路只对了一半

不能win的结论是正确的,但是win的结论不止排除这一个条件

将这个人与其他人的条件列式

如果都win的话,则满足 x/v+y/u+(k-x-y)/w(i的)

#include    
#include    
#include    
using namespace std;  
const double eps = 1e-8;  
  
struct Point  
{  
    double x,y;  
    Point(double x=0,double y=0):x(x),y(y) {}  
};  
  
typedef Point Vector;  
  
Vector operator - (Point A, Point B)  
{  
    return Vector(A.x-B.x, A.y-B.y);  
}  
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 ang0;  
}  
  
Point GetIntersection(Line a, Line b)  
{  
    Vector u = a.p-b.p;  
    double t = Cross(b.v, u)/Cross(a.v, b.v);  
    return Point(a.p.x+a.v.x*t, a.p.y+a.v.y*t);  
}  
  
int BPMJ(Line *L, int n, Point *poly)  
{  
    sort(L,L+n);  
    int first,last;  
    Point *p = new Point[n];  
    Line *q = new Line[n];  
    q[first=last=0] = L[0];  
    for(int i=1; i=u[j] && v[i]>=v[j] && w[i]>=w[j])  
                        continue;  
                    else if(j!=i)  
                    {  
                        double A=k/v[j]-k/v[i]-k/w[j]+k/w[i];  
                        double B=k/u[j]-k/u[i]-k/w[j]+k/w[i];  
                        double C=k/w[j]-k/w[i];  
                        if(fabs(A)>fabs(B))  
                            p=Point(-C/A,0);  
                        else  
                            p=Point(0,-C/B);  
                        Vector v(B,-A);  
                        L[ct++] = Line(p,v);  
                    }  
                }  
                L[ct++] = Line(Point(0,0), Vector(0,-1));  
                L[ct++] = Line(Point(0,0), Vector(1,0));  
                L[ct++] = Line(Point(0,1), Vector(-1,1));  
                if(BPMJ(L,ct,poly))printf("Yes\n");  
                else printf("No\n");  
            }  
        }  
    }  
    return 0;  
}  

#include 
#include 
#include 
using namespace std;
const double eps = 1e-8;

struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {}
};

typedef Point Vector;

Vector operator - (Point A, Point B)
{
    return Vector(A.x-B.x, A.y-B.y);
}
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 ang0;
}

Point GetIntersection(Line a, Line b)
{
    Vector u = a.p-b.p;
    double t = Cross(b.v, u)/Cross(a.v, b.v);
    return Point(a.p.x+a.v.x*t, a.p.y+a.v.y*t);
}

int BPMJ(Line *L, int n, Point *poly)
{
    sort(L,L+n);
    int first,last;
    Point *p = new Point[n];
    Line *q = new Line[n];
    q[first=last=0] = L[0];
    for(int i=1; i=u[j] && v[i]>=v[j] && w[i]>=w[j])
                        continue;
                    else if(j!=i)
                    {
                        double A=k/v[j]-k/v[i]-k/w[j]+k/w[i];
                        double B=k/u[j]-k/u[i]-k/w[j]+k/w[i];
                        double C=k/w[j]-k/w[i];
                        if(fabs(A)>fabs(B))
                            p=Point(-C/A,0);
                        else
                            p=Point(0,-C/B);
                        Vector v(B,-A);
                        L[ct++] = Line(p,v);
                    }
                }
                L[ct++] = Line(Point(0,0), Vector(0,-1));
                L[ct++] = Line(Point(0,0), Vector(1,0));
                L[ct++] = Line(Point(0,1), Vector(-1,1));
                if(BPMJ(L,ct,poly))printf("Yes\n");
                else printf("No\n");
            }
        }
    }
    return 0;
}


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇11661 - Burger Time? 下一篇poj3348 Cows 凸包+多边形面积 水..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·一篇说人话的文章, (2025-12-27 07:50:09)
·Python Web框架哪家 (2025-12-27 07:50:06)
·基于Python的数据分 (2025-12-27 07:50:03)
·深入理解 Java 集合 (2025-12-27 07:22:48)
·Java集合框架全面解 (2025-12-27 07:22:45)