2019 ICPC Asia Nanjing Regional K. Triangle

题目链接：https://nanti.jisuanke.com/t/42405

题意：一个三角形三个顶点坐标和另一个点P坐标，求Q点坐标使得PQ平分三角形面积，若P不在三角形边上，输出-1
————————————————————————————————
若P点在AB边上且靠近A，则Q点一定在BC边上
(S_{PBQ}=frac{|PB|*|QB|*sin(B)}{2})

(S_{ABC}=frac{|AB|*|CB|*sin(B)}{2})

(2*S_{PBQ}=S_{ABC})

所以(|QB|=frac{|AB|*|CB|}{2*|PB|})，在BC上二分求出Q坐标即可
对于其他情况 可以转化为这一种情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double esp=1e-7;
struct po
{
    double x,y;
    po(double _x=0,double _y=0):x(_x),y(_y){}
}p[3],pp;
typedef struct po pi;
double a1,a2,a3,b1,b2,b3;
double dis(pi a,pi b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool inl(pi np,pi a,pi b){return (np.y-a.y)*(np.x-b.x)==(np.x-a.x)*(np.y-b.y);}
string check(pi np)
{
    if(inl(np,p[0],p[1])&&fabs(dis(np,p[0])+dis(np,p[1])-dis(p[0],p[1]))<esp)
    {
        if(dis(np,p[0])>dis(np,p[1]))
        return "012";
        return "102";
    }
    if(inl(np,p[0],p[2])&&fabs(dis(np,p[0])+dis(np,p[2])-dis(p[0],p[2]))<esp)
    {
        if(dis(np,p[0])>dis(np,p[2]))
        return "021";
        return "201";
    }
    if(inl(np,p[2],p[1])&&fabs(dis(np,p[2])+dis(np,p[1])-dis(p[1],p[2]))<esp)
    {
        if(dis(np,p[2])>dis(np,p[1]))
        return "210";
        return "120";
    }
    return "-1";
}
int main()
{
    int t ;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y,&pp.x,&pp.y);
        string opt=check(pp);
        if(opt=="-1")
            puts("-1");
        else
        {
            pi l=p[opt[0]-'0'],r=p[opt[2]-'0'],tb=p[opt[0]-'0'];
            double bp=2*dis(p[opt[0]-'0'],pp),ba=dis(p[opt[0]-'0'],p[opt[1]-'0']),bc=dis(p[opt[0]-'0'],p[opt[2]-'0']);
            pi mid;
            while(dis(l,r)>esp)
            {
                mid=pi((l.x+r.x)/2,(l.y+r.y)/2);
                if(dis(tb,mid)*bp-ba*bc>0)
                    r=mid;
                else
                    l=mid;
            }
            printf("%.12f %.12f
",mid.x,mid.y);
        }
    }
    return 0;
}