[Codeforces 23D] Tetragon

Brief Intro:

给3条相同长度的边的中点，问是否存在一个严格凸四边形

 

Algorithm:

明显只要求出一个点就能利用对称性算出其他点的坐标

设中点K,L,M分别在边AB,BC,CD上，易知B、C分别在KL、LM的垂直平分线上

 

但仍需一个点才能确定B点的位置

于是我们想办法将现有的信息整合：做M关于L的对称点M’，从而发现M’B=KB=LB

接下来手算出KL、LM’的垂直平分线的直线方程

用((b1c2-b2c1)/(a1b2-a2b1)，(a2c1-a1c2)/(a1b2-a2b1))求出交点即可

 

注意：求完4个点后，仍要判断正确性（是否为凸四边形）：

           判断顺时针的4个三角形方向是否相同（叉积的正负性是否相同）

 

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second

const double eps=1e-8;
typedef pair<double,double> P;
int T;
P a,b,c;

double Cross(P a,P b,P c)
{
    return (a.X*b.Y+b.X*c.Y+c.X*a.Y)-(b.X*a.Y+c.X*b.Y+a.X*c.Y);
}

inline int Read()
{
    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f|=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

P read()
{
    P t;t.X=Read();t.Y=Read();
    return t;
}

bool check(P x,P y,P z)
{
    double A0=2*(x.X-y.X),A1=2*(y.X-z.X);
    double B0=2*(x.Y-y.Y),B1=2*(y.Y-z.Y);
    double C0=y.X*y.X-x.X*x.X+y.Y*y.Y-x.Y*x.Y;
    double C1=-3*(y.X*y.X+y.Y*y.Y)-(z.X*z.X+z.Y*z.Y)+4*(y.X*z.X+y.Y*z.Y);
    
    P A,B,C,D;
    A.X=(B0*C1-B1*C0)/(A0*B1-A1*B0);A.Y=(A1*C0-A0*C1)/(A0*B1-A1*B0);
    B.X=2*y.X-A.X;B.Y=2*y.Y-A.Y;
    C.X=2*x.X-A.X;C.Y=2*x.Y-A.Y;
    D.X=2*z.X-B.X;D.Y=2*z.Y-B.Y;
    
    double P1=Cross(C,A,B),P2=Cross(A,B,D),P3=Cross(B,D,C),P4=Cross(D,C,A); //判断方向
    
    if((P1>0 && P2>0 && P3>0 && P4>0) || (P1<0 && P2<0 && P3<0 && P4<0))
    {
        printf("YES\n");
        printf("%0.10lf %0.10lf ",A.X,A.Y);
        printf("%0.10lf %0.10lf ",B.X,B.Y);
        printf("%0.10lf %0.10lf ",D.X,D.Y);
        printf("%0.10lf %0.10lf\n",C.X,C.Y);
        return true;
    }
    return false;
}

bool solve()
{
    if(Cross(a,b,c) && (check(a,b,c) || check(c,a,b) || check(b,c,a))) 
        return true;
    return false;
}

int main()
{
    scanf("%d",&T);
    
    while(T--)
    {
        a=read();b=read();c=read();
        if(!solve())  printf("NO\n\n");
    }
    return 0;
}

 

Review

1、对凸四边形的判断：

顺时针旋转的每个三角形叉积的正负性是否相同

 

2、学会利用对称点的方式整合信息