首页 > 代码库 > HDU1700 Points on Cycle (最大内接三角形)

HDU1700 Points on Cycle (最大内接三角形)

2024-08-05 23:52:05   209人阅读

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1700


题意：

一个圆心为原点的圆，告诉你圆上一点，求圆上另外两点的坐标使圆的面积最大


分析：

 三角形的面积由底边和高两个因素决定，不管底边所在弦有多少，
但其高只有经过圆心的为最大，
故毫无质疑必须是等腰三角形。
设等腰三角形ABC,高AH，圆心O，AO=BO=R，OH=AH-AO，设高为x,
BH=√[R^2-(x-R)^2]=√（2Rx-x^2),
∴S=x√（2Rx-x^2),
dS=√（2Rx-x^2)+(1/2)*(2Rx-x^2)^(-1/2)*(2R-2x)*x=(2Rx-x^2+Rx-x^2)/√（2Rx-x^2)=0,
2x^2-3Rx=0,
x=3R/2,根据实际问题，该驻点有极大值，
即当x=3R/2时有最大面积，而高AH=3R/2，正是正三角形，
∴当圆内接正三角形时具有最大面积。 

 已知A(a,b), 设B(x,y),,
cos(2pi/3)=向量OA*向量OB/|OA|*|OB|;
( ax+b*y ) =  -1/2 * R*R; --------1)

a*a + b*b = R*R;  -----------2)

x*x + y*y = R*R   -----------3)

一二三式联立可以解出两个点的坐标，注意x=0的时候

代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        double x1,y1,r;
        scanf("%lf%lf",&x1,&y1);
        r = x1*x1+y1*y1;
        double a = 1;
        double b = y1;
        double c = r/4-x1*x1;
        double delta = b*b-4*a*c;
        double ansy1 = (-b-sqrt(delta))/2/a;
        double ansy2 = (-b+sqrt(delta))/2/a;
        double ansx1,ansx2;
        if(fabs(x1)<=1e-7){
            ansx1 = -sqrt(r-ansy1*ansy1);
            ansx2 =  sqrt(r-ansy2*ansy2);
        }
        else{
            ansx1 = (-r/2-y1*ansy1)/x1;
            ansx2 = (-r/2-y1*ansy2)/x1;
        }
        printf("%.3lf %.3lf %.3lf %.3lf\n",ansx1,ansy1,ansx2,ansy2);
    }
    return 0;
}





HDU1700 Points on Cycle (最大内接三角形)


联系
我们