Triangle ~~ 叉积

最新推荐文章于 2021-09-27 14:23:09 发布

Daowuu

最新推荐文章于 2021-09-27 14:23:09 发布

阅读量459

点赞数 1

分类专栏：计算几何

本文链接：https://blog.csdn.net/Long_hen/article/details/106786559

版权

计算几何专栏收录该内容

3 篇文章

订阅专栏

本文探讨了如何在三角形中找到一条线段，使其两端分别位于三角形边界上，并将三角形分为面积相等的两部分。文章提供了一种算法，首先确定给定点在三角形哪条边上，然后计算另一端点的位置。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目超链接

One day, ABC and DD found a triangular wheat field, and they decide to cut it into two pieces with the same area with a segment. Because of various reasons, one of the endpoints of the division line is fixed at (px,py). Now you are asked to find the other endpoint of the segment.
If the given endpoint does not lie on the boundary of the wheat field, the problem should be regarded as invalid. The other endpoint required should also locate on the boundary.

Input

The input provides several test cases and the first line of the input contains a single integer T (1≤T≤1000000) indicating the number of cases.
For each test case, eight integers x1,y1,x2,y2,x3,y3,px and py are given in a line, where (x1,y1),(x2,y2) and (x3,y3)describe the coordinates of vertices for the given triangle wheat field which are guaranteed to be not colinear, and (px,py) is the given endpont of the segment. All coordinates are integers in the range [0,100000].

Output

For each test case, output the coordinate of the other endpoint of the division segment, or output the number -1 if the problem, in this case, is invalid.
Formally, if your answer is aaa and the jury’s answer is bbb, then your answer will be considered correct if and only if

本题答案不唯一，符合要求的答案均正确
样例输入

2
0 0 1 1 1 0 1 0
0 0 1 1 1 0 2 0

样例输出

0.500000000000 0.500000000000
-1

题意：给你三角形的三个顶点，再给你一个点，若该点在三角形上，则再在这个三角形上找一点，连接着两个点使得三角形被分成面积相等的两半。否则输出-1。
思路：我们只讨论询问点在三角形上的情况，首先确定询问点在哪条边上，再确定答案点在哪条边上。（都是通过叉积判断的），具体实现看代码：

#include<bits/stdc++.h>
#define eps 1e-8
#define zero(x) (!(((x)>0?(x):-(x))<eps)) // x = 0 返回 false

using namespace std;
struct point {double x, y; point(){} point(double x, double y): x(x), y(y){}};

double cross(point a, point b, point c) {
  return fabs((b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x));
}

void solve(point a, point b, point c, point d, double S) {
  double k = S / cross(b, d, c); // S = cross（kcb * db）
  printf("%.12f %.12f\n",(c.x-b.x)*k + b.x, (c.y-b.y)*k + b.y);
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    point a, b, c, d;
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
    double S=cross(a,b,c),s1=cross(d,a,b),s2=cross(d,b,c),s3=cross(d,c,a);
    if ((zero(S-s1-s2-s3))||zero(s1)&&zero(s2)&&zero(s3)) printf("-1\n");
    else if (!zero(s1)) {if (s2>s3) solve(a,b,c,d,S/2); else solve(b,a,c,d,S/2);}
    else if (!zero(s2)) {if (s1>s3) solve(c,b,a,d,S/2); else solve(b,c,a,d,S/2);}
    else if (!zero(s3)) {if (s1>s2) solve(c,a,b,d,S/2); else solve(a,c,b,d,S/2);}
  }
  return 0;
}