Codeforences 23D Tetragon

【题意】给定3个点，判定是否存在一个严格凸四边形，使得其中三条边的中点恰好是这3个点。不超过50000组数据。 坐标范围比较小。

【解题方法】

假设四边形四个点是a , b , c , d。中点为k , l , m分别为ab , bc , cd的中点。

那么作m点关于l点的对称点m‘，容易得到m’b = bl = bk ，所以b是三角形klm’的外心。

那么剩下点就可以求出，然后 判断下ab = bc = cd是否成立，以及用叉积判断下是否为凸包

关键在于求三角形的外心，这个东西怎么求呢？由于外心是三个垂直平分线的交点，那么我们找任意两条垂直平分线就可以了，那么直线可以写成中点坐标+t*方向向量，然后把这两个方程联立求解就可以解出三角形的外心了。还有一种方法是通过海伦公式算的，把这两种方法写出来。。。

【三角形外心求解】

//海伦公式，精度比较差
Point Circle_Point(Point A, Point B, Point C)
{
    double aa = dist(B, C);
    double bb = dist(A, C);
    double cc = dist(A, B);
    double p = (aa + bb + cc) / 2.0;
    double S = sqrt(p*(p-aa)*(p-bb)*(p-cc));
    R = (aa*bb*cc) / (4.0*S);
    double t1 = (A.x*A.x+A.y*A.y-B.x*B.x-B.y*B.y)/2.0;
    double t2 = (A.x*A.x+A.y*A.y-C.x*C.x-C.y*C.y)/2.0;
    Point center;
    center.x = (t1*(A.y-C.y)-t2*(A.y-B.y))/((A.x-B.x)*(A.y-C.y)-(A.x-C.x)*(A.y-B.y));
    center.y = (t1*(A.x-C.x)-t2*(A.x-B.x))/((A.y-B.y)*(A.x-C.x)-(A.y-C.y)*(A.x-B.x));
    return center;
}

//直接利用中垂线，求解两个二元一次方程， 精度高

Point Circumcenter(Point a, Point b){
        double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2.0;
        double a2 = x - a.x, b2 = y - a.y, c2 = (a2 * a2 + b2 * b2 ) / 2.0;
        double d = a1 * b2 - a2 * b1;
        return Point(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
    }

【AC代码】

#include <bits/stdc++.h>
using namespace std;
const double eps1 = 1e-5;
const double eps2 = 1e-8;
#define REP(i, n) for(int i = 0; i < n; i++)
struct Point{
    double x, y;
    Point(){}
    Point(double x, double y):x(x), y(y){}
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    double dist(Point a){
        return sqrt((x - a.x)*(x - a.x) + (y - a.y)*(y - a.y));
    }
    Point zz(Point a){
        return Point(x*2 - a.x, y*2 - a.y);
    }
    Point Circumcenter(Point a, Point b){
        double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2.0;
        double a2 = x - a.x, b2 = y - a.y, c2 = (a2 * a2 + b2 * b2 ) / 2.0;
        double d = a1 * b2 - a2 * b1;
        return Point(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
    }
};
double Cross(Point p, Point p1, Point p2){
    return (p.x - p1.x) * (p.y - p2.y) - (p.y - p1.y) * (p.x - p2.x);
}
bool issame(double x, double y){
    if(fabs(x - y) < eps2){
        return true;
    }
    else{
        return false;
    }
}
bool Isconvex(Point a, Point b, Point c, Point d){
    double t1 = Cross(a, b, c);
    double t2 = Cross(b, c, d);
    double t3 = Cross(c, d, a);
    double t4 = Cross(d, a, b);
    if(t1 * t2 <= eps1 || t2 * t3 <= eps1 || t3 * t4 <= eps1 || t4 * t1 <= eps1) return false;
    return true;
}
bool solve(Point k, Point l, Point m)
{
    if(Cross(k, l, m) == 0) return false;
    Point b = k.Circumcenter(l.zz(m), l), a = k.zz(b), c = l.zz(b), d = m.zz(c);
    if(!issame(a.dist(b), b.dist(c)) || !issame(b.dist(c), c.dist(d))) return false;
    if(!Isconvex(a, b, c, d)) return false;
    printf("YES\n");
    printf("%.9f %.9f %.9f %.9f %.9f %.9f %.9f %.9f\n", a.x, a.y, b.x , b.y, c.x, c.y, d.x, d.y);
    return true;
}
int main()
{
    Point k, l, m;
    int T;
    scanf("%d", &T);
    REP(i, T){
        k.input(), l.input(), m.input();
        if(solve(k, l, m)) continue;
        if(solve(k, m, l)) continue;
        if(solve(l, k, m)) continue;
        if(solve(l, m, k)) continue;
        if(solve(m, k, l)) continue;
        if(solve(m, l, k)) continue;
        printf("NO\n\n");
    }
    return 0;
}