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
*/