欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

19 南京 icpc K. Triangle//计算几何+分类讨论模拟+二分

程序员文章站 2022-03-02 10:28:24
...

题目

题意

给一个三角形,给一个点,求三角形边界上另外一点,使得两个点连线把三角形分成面积相等的两块。

思路

先判断给的点在三角形点上或者边上或者不合法。
如果在点上:
找到对边,建立二元一次方程(我用点斜式,需要特判平行于y轴的情况),然后取中点。
如果在边上:
找到对顶点和较远的一点,在这两个边组成的线段上二分(同样需要考虑平行于y轴的情况),我二分了横坐标,此时需要考虑横坐标变大面积变大还是变小,也需要分类。

/*   Author : Rshs
 *   Data : 2020-01-14-09.49
 */
#include<bits/stdc++.h>
using namespace std;
#define FI first
#define SE second
#define LL long long
#define MP make_pair
#define PII pair<int,int>
#define SZ(a) (int)a.size()
const double pai = acos(-1);
const double eps = 1e-10;
const LL mod = 1e9 + 7;
const int MXN = 1e6 + 5;
int eq(double a, double b) {
    if(abs(a - b) < eps) return 1;
    return 0;
}
double fk(pair<double, double> x, pair<double, double> y) {
    if(x.FI == y.FI) return 0;
    return (x.SE - y.SE) / (x.FI - y.FI);
}
double fb(pair<double, double> x, pair<double, double> y) {
    if(x.FI == y.FI) return 0;
    return (x.FI * y.SE - y.FI * x.SE) / (x.FI - y.FI);
}
double dis(pair<double, double> x, pair<double, double> y) {
    return sqrt((x.FI - y.FI) * (x.FI - y.FI) + (x.SE - y.SE) * (x.SE - y.SE));
}
double tare(pair<double, double> x, pair<double, double> y, pair<double, double>z) {
    double x1 = x.FI, y1 = x.SE, x2 = y.FI, y2 = y.SE, x3 = z.FI, y3 = z.SE;
    return abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
}
pair<double, double> a[3], e;
void Main(int avg) {
    for(int i = 0; i < 3; i++) {
        int sa, sb;
        scanf("%d%d", &sa, &sb);
        a[i].FI = sa, a[i].SE = sb;
    }
    sort(a, a + 3);
    int sa, sb;
    scanf("%d%d", &sa, &sb);
    e.FI = sa, e.SE = sb;
    for(int i = 0; i < 3; i++) {
        if(eq(a[i].FI, e.FI) && eq(a[i].SE, e.SE)) {
            vector<pair<double, double>>v;
            for(int j = 0; j < 3; j++) {
                if(i == j)continue;
                v.push_back(a[j]);
            }
            if(v[0].FI==v[1].FI){
                printf("%.8lf %.8lf\n", v[0].FI, (v[0].SE+v[1].SE)/2);
                return ;
                continue;
            }
            double k = fk(v[0], v[1]);
            double b = fb(v[0], v[1]);
            double midx = (v[0].FI + v[1].FI) / 2;
            double midy = k * midx + b;
            printf("%.8lf %.8lf\n", midx, midy);
            return ;
        }
    }
    for(int i = 0; i < 3; i++) {
        vector<pair<double, double>>v, lv;
        for(int j = 0; j < 3; j++) {
            if(i == j) continue;
            v.push_back(a[j]);
        }
        if(v[0].FI==v[1].FI){
            if(e.FI!=v[0].FI) continue;
            if(e.SE<v[0].SE||e.SE>v[1].SE)continue;
        }
        else {
            if(e.FI < v[0].FI || e.FI > v[1].FI) continue;
            double k = fk(v[0], v[1]);
            double b = fb(v[0], v[1]);
            double y = k * e.FI + b;
            if(!eq(y, e.SE)) continue;
        }
        if(dis(v[0], e) > dis(v[1], e)) {//找离得远的
            lv.push_back(v[0]);
        } else {
            lv.push_back(v[1]);
        }
        lv.push_back(a[i]);
        if(lv[0].FI==lv[1].FI){
            if(lv[0].SE<lv[1].SE){
                double l = lv[0].SE, r = lv[1].SE, ans;
                for(int i = 1; i <= 100; i++) {
                    double midy = (l + r) / 2.0;
                    double midx = lv[0].FI;
                    if(tare(a[0], a[1], a[2]) / 2 <= tare(MP(midx, midy), lv[0], e)) ans = midy, r = midy;
                    else l = midy;
                }
                printf("%.8lf %.8lf\n", lv[0].FI, ans);
            }
            else{
                double l = lv[1].SE, r = lv[0].SE, ans;
                for(int i = 1; i <= 100; i++) {
                    double midy = (l + r) / 2.0;
                    double midx = lv[0].FI;
                    if(tare(a[0], a[1], a[2]) / 2 <= tare(MP(midx, midy), lv[0], e)) ans = midy, l = midy;
                    else r = midy;
                }
                printf("%.8lf %.8lf\n", lv[0].FI, ans);
            }
        }
        else {
            if(lv[0].FI < lv[1].FI) {
                double k = fk(lv[0], lv[1]);
                double b = fb(lv[0], lv[1]);
                double l = lv[0].FI, r = lv[1].FI, ans;
                for(int i = 1; i <= 100; i++) {
                    double midx = (l + r) / 2.0;
                    double midy = k * midx + b;
                    if(tare(a[0], a[1], a[2]) / 2 <= tare(MP(midx, midy), lv[0], e)) ans = midx,r = midx;
                    else l = midx;
                }
                printf("%.8lf %.8lf\n", ans, ans * k + b);
            } else {
                double k = fk(lv[0], lv[1]);
                double b = fb(lv[0], lv[1]);
                double l = lv[1].FI, r = lv[0].FI, ans;
                for(int i = 1; i <= 100; i++) {
                    double midx = (l + r) / 2.0;
                    double midy = k * midx + b;
                    if(tare(a[0], a[1], a[2]) / 2 <= tare(MP(midx, midy), e, lv[0])) ans = midx, l = midx;
                    else r = midx;
                }
               // cout<<tare(MP(ans, ans*k+b), e, lv[0])<<'\n';
                printf("%.8lf %.8lf\n", ans, ans * k + b);
            }
        }
        return ;
    }
    puts("-1");
}
int main() {
    int cas;
    cin >> cas;
    for(int i = 1; i <= cas; i++)Main(i);
    return 0;
}
/*
10
0 0 2 2 2 0 2 1
0 0 4 4 4 0 4 1
*/

相关标签: 几何