Pan's Labyrinth

题目链接

题目大意：给n个点，求任意三角形的最大高

关键点：分析出来三角形的底可以是任意两个点组成，但是对应的最优高的第三个点一定在凸包上，那么就可以在凸包上进行旋转卡壳，整体复杂度为O(n * n * log(n))

struct Point
{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y) { }
    inline void read()
    {
        scanf("%lf %lf", &x, &y);
    }
} t;
typedef vector<Point> Polygon;
typedef Point Vector;

double torad(double deg)
{
    return deg / 180 * PI;
}
inline int dcmp(double x)
{
    if(fabs(x) < EPS) return 0;
    else return x < 0 ? -1 : 1;
}

typedef vector<Point> Polygon;
typedef Point Vector;

inline Vector operator+ (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
inline Vector operator- (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
inline Vector operator* (Vector A, double p) { return Vector(A.x * p, A.y * p); }
inline Vector operator/ (Vector A, double p) { return Vector(A.x / p, A.y / p); }

inline bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
inline bool operator == (Point a, Point b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }

inline double Dot(Vector A, Vector B){ return A.x * B.x + A.y * B.y;}
inline double Length(Vector A) { return sqrt(Dot(A, A)); }
inline double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
inline Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x); } //垂直法向量

//点到直线距离
inline double DistanceToLine(Point P, Point A, Point B)
{
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2)) / Length(v1); // 如果不取绝对值，得到的是有向距离
}

// 点集凸包
// 如果希望在凸包的边上有输入点，把两个 <= 改成 <
// 注意：输入点集会被修改
vector<Point> ConvexHull(vector<Point>& p)
{
    // 预处理，删除重复点
    sort(p.begin(), p.end());

    int n = p.size();
    int m = 0;
    vector<Point> ch(n+1);
    for(int i = 0; i < n; i++)
    {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i--)
    {
        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    ch.resize(m);
    return ch;
}

// 有向直线。它的左边就是对应的半平面
struct Line
{
    Point p, q;    // 直线上任意一点,p作为起点
    Vector v;   // 方向向量
    double ang; // 极角，即从x正半轴旋转到向量v所需要的角（弧度）
    Line() {}
//    Line(Point P, Vector v):p(P),v(v)
//    {
//        ang = atan2(v.y, v.x);
//    }
    Line(Point P, Point Q):p(P), q(Q)
    {
        v = q - p;
        ang = atan2(v.y, v.x);
    }
    inline bool operator < (const Line& L) const
    {
        return ang < L.ang;
    }
    inline Point point(double t)
    {
        return p + v * t;
    }
    inline Line move(double d)
    {
        return Line(p + Normal(v) * d, v);
    }
    inline void read()
    {
        Point q;
        p.read(), q.read();
        v = q - p;
        ang = atan2(v.y, v.x);
    }
};

vector<Point> ipt, convex;
vector<Line> line;

int main()
{
//    freopen("in.txt", "r", stdin);
    int n;
    while (~RI(n))
    {
        ipt.clear(), convex.clear(), line.clear();
        REP(i, n)
        {
            t.read();
            ipt.push_back(t);
        }

        convex = ConvexHull(ipt);
        FF(i, 0, n)
        {
            FF(j, i + 1, n)
            {
                line.push_back(Line(ipt[i], ipt[j]));
                line.push_back(Line(ipt[j], ipt[i]));
            }
        }
        sort(all(line));

        int index = 0;

//	  这是第一次的错误写法,邪恶的过了.但是觉得如果找到的第一个点刚好下一个就是在直线上或者在直线右边,那么第一条直线可能就出现了问题
//        while (Cross(convex[index] - line[0].p, line[0].v) > 0)
//        {
//            index = (index + 1) % convex.size();
//        }


	//此处找到了在第一条直线非右边的第一个点
        while (Cross(convex[index] - line[0].p, line[0].v) > 0 && Cross(convex[(index + 1) % convex.size()] - line[0].p, line[0].v) <= 0)
        {
            index = (index + 1) % convex.size();
        }
        double ans = -1e100;
        REP(i, (int)line.size())
        {
            while (Cross(convex[(index + 1) % convex.size()] - line[i].p, line[i].v) < 0 && fabs(Cross(convex[index] - line[i].p, line[i].v)) < fabs(Cross(convex[(index + 1) % convex.size()] - line[i].p, line[i].v)))
            {
                index = (index + 1) % convex.size();
            }
            ans = max(ans, DistanceToLine(convex[index], line[i].p, line[i].q));
        }
        printf("%.5f\n", ans);
    }
    return 0;
}

Pan's Labyrinth,布布扣,bubuko.com

Pan's Labyrinth

原文：http://blog.csdn.net/wty__/article/details/20554389