整理的算法模板合集： ACM模板

K.Triangle

用板子判断点是否在线段上即可。紫书的板子有点问题，判断是否在线段上的时候应该是<=才能A，书上是 < …
对于第二问我们先特判一下特殊的情况，也就是p点在三角形端点的时候答案就是端点对边的中点。

然后我们用一个直线玩一下三角形就发现，从特殊的情况（端点到对边中点）出发，我们假设端点是A，当p点在线段AB上的时候，若P点靠近A点，那么我们的直线就会转到靠近B点，当P点靠近B点的时候，我们的直线就会转到靠近C点，因为情况不定，所以我们可以将点换到都是在AB上的情况。（我们直接判断然后swap就行了，不会影响最终的答案）。将各种情况统一了以后才能编码解决嘛。

我们统一了以后，考虑如何找到这个点使得线段PQ可以均分大三角形的面积，直接枚举找答案肯定是不可取的，我们发现这个直线转动可能有单调性，求解最终的答案，考虑二分答案。我们直接二分点Q距离C点的距离，这样线段就会把整个三角形分成了一个小三角形和一个四边形，我们可以很轻松地求得小三角形的面积，轻松判断小三角形的面积是否为大三角形的面积的一半，所以答案的解法就出来了， 我们考虑二分答案，先用海伦公式求大三角形的面积，然后根据s = absinc/2可以求得角B的大小，然后继续用这个公式求小三角形的面积，比较是否等于大三角形的面积的一半，二分出答案以后我们要求该点的坐标，因为是在三角形上，我们可以直接按照比例，BC边与BQ边的长度之比，求得Q点的坐标。（我们这里B和C谁在左谁在右都无所谓，我们直接用B的坐标-C的坐标，按比例缩小了以后，直接加上C的坐标，这样C在左边差就是正数，C往右移（B的方向），C在右边差就是负数，C往左移动（B的方向））。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<bitset>
#include<queue>
#include<cmath>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;//卡精度
typedef pair<int,int> PII;

const int N = 3e4+7, M = 3e5 + 7;
const ll mod = 1e9+7;
const ll INF = 1e15+7;
const double eps = 1e-8;//可近似为趋近为 0 可以根据定义求导时使用
const int base = 131;//base = 13331 // hash
int t, n, m;
//判断点是否在直线上/线段2.7
//在三角形的三个线段上寻找另一个点连接的直线将三角形切开成两块面积相等
double ac, ab, bc, pa, pb, pc, ap, bp;
double area, sina, sinb, sinc;

struct Point
{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }
}a, b, c, p, q;

typedef Point Vector ;

Vector operator + (Vector a, Vector b)
{
    return Vector(a.x + b.x, a.y + b.y);
}

Vector operator - (Point a, Point b)
{
    return Vector(a.x - b.x, a.y - b.y);
}

int dcmp(double x)
{
    if(fabs(x) < eps)
        return 0;
    else return x < 0 ? -1 : 1;
}

bool operator == (const Point& a, Point& b){
    return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);
}

double Dot(Point A, Point B)
{
    return A.x * B.x + A.y * B.y;
}

double Cross(Point A, Point B)
{
    return A.x * B.y - A.y * B.x;
}

bool on_segment(Point p, Point a, Point b)
{
    return dcmp(Cross(a - p, b - p)) == 0 && dcmp(Dot(a - p, b - p)) <= 0;
}

bool onSegment(Point Pi, Point Pj, Point Q)
{
    if((Q.x - Pi.x) * (Pj.y - Pi.y) == (Pj.x - Pi.x) * (Q.y - Pi.y)  //叉乘
       //保证Q点坐标在pi,pj之间
       && min(Pi.x , Pj.x) <= Q.x && Q.x <= max(Pi.x , Pj.x)
       && min(Pi.y , Pj.y) <= Q.y && Q.y <= max(Pi.y , Pj.y))
        return true;
    else
        return false;
}

double get_dist(Point a, Point b)
{
    double fa = a.x - b.x;
    double fb = a.y - b.y;
    return sqrt(fa * fa + fb * fb);
}

bool check(double x, double sin){
    double ans = bp * sin * (bc - x);//三角形面积，除以2之后还要乘以2
    return ans < area;
}

void solve()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &p.x, &p.y);
    //if(on_segment(p, a, b))cout << "OK" << endl;
    if(!on_segment(p, a, b) && !on_segment(p, a, c) && !on_segment(p, b, c)){
        puts("-1");
        return ;
    }

    if(p == a){
        double fx = (b.x + c.x) / 2.0;
        double fy = (b.y + c.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }
    else if(p == b){
        double fx = (a.x + c.x) / 2.0;
        double fy = (a.y + c.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }
    else if(p == c){
        double fx = (a.x + b.x) / 2.0;
        double fy = (a.y + b.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }

    if(on_segment(p, a, b)){ }
    else if(on_segment(p, a, c))swap(b, c);
    else if(on_segment(p, b, c))swap(a, c);

    //统一让p点里a近一些
    if(get_dist(p, a) > get_dist(p, b))swap(a, b);


    ac = get_dist(a, c);
    ab = get_dist(a, b);
    bc = get_dist(b, c);
    ap = get_dist(a, p);
    bp = get_dist(b, p);
    //pc = get_dist(p, c);

    double k = (ab + ac + bc) / (double)2;
    area = sqrt(k * (k - ab) * (k - ac) * (k - bc));
    sina = area * 2 / ac / ab;
    sinb = area * 2 / ab / bc;
    sinc = area * 2 / ac / bc;

    double l = 0.0, r = bc;
    while(l + eps < r){
        double mid = (l + r) / (double)2;
        if(check(mid, sinb))r = mid;
        else l = mid;
    }

    double len = l;

    q.x = (b.x - c.x) * len / (bc) + c.x;
    q.y = (b.y - c.y) * len / (bc) + c.y;
    printf("%.10f %.10f\n", q.x, q.y);
    return ;
}


int main()
{
    scanf("%d", &t);
    while(t -- ){
        solve();
    }
    return 0;
}