URAL 1043 三角形外接圆

简介:

题意:给出一个圆弧上的三个点,求出一个边平行于坐标轴面积最小的矩形并且这个矩形可以给这个圆弧覆盖掉,求矩形面积。

步骤:

1.先求出给出三点围城三角形的外接圆,圆弧就是这个圆的一部分。

2.找出外接圆的上下左右四个端点。

3.枚举四个端点如果在弦ab 跟c同侧那么圆弧肯定过这一点,记下这点的极值。用叉积判断同号即可。

4.特判端点大于1000的情况然后输出面积即可。

这题精度好难调。求外接圆圆心一步求出。分成变量存可能有精度问题,eps必须要有,不然会出错。WA10 5 6次。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct point
{
    double x,y;
};
const double eps=1e-9;
double TriangleArea(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return fabs((pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y))/2;
}
double dir(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
double Dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    point a,b,c;
    double r;
    while(~scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y))
    {
        r=Dis(a,b)*Dis(a,c)*Dis(b,c)/TriangleArea(a,b,c)/4;
        point center;
        center.x=((a.x*a.x+a.y*a.y-b.x*b.x-b.y*b.y)/2.0*(a.y-c.y)-(a.x*a.x+a.y*a.y-c.x*c.x-c.y*c.y)/2.0*(a.y-b.y))/((a.x-b.x)*(a.y-c.y)-(a.x-c.x)*(a.y-b.y));
        center.y=((a.x*a.x+a.y*a.y-b.x*b.x-b.y*b.y)/2.0*(a.x-c.x)-(a.x*a.x+a.y*a.y-c.x*c.x-c.y*c.y)/2.0*(a.x-b.x))/((a.y-b.y)*(a.x-c.x)-(a.y-c.y)*(a.x-b.x));
        int lx,rx,uy,dy;
        lx=(int)floor(center.x-r+eps),dy=(int)floor(center.y-r+eps),rx=(int)ceil(center.x+r-eps),uy=(int)ceil(center.y+r-eps);
        point edge[4];
        edge[0].y=edge[1].y=center.y,edge[0].x=center.x-r,edge[1].x=center.x+r;
        edge[2].x=edge[3].x=center.x,edge[2].y=center.y-r,edge[3].y=center.y+r;
        int miny=min(a.y,b.y),maxy=max(a.y,b.y),minx=min(a.x,b.x),maxx=max(a.x,b.x);
        for(int i=0; i<4; i++)
            if(dir(a,c,b)*dir(a,edge[i],b)>=-eps)
            {
                if(i==2)miny=dy;
                if(i==3)maxy=uy;
                if(i==0)minx=lx;
                if(i==1)maxx=rx;
            }
        maxx=min(maxx,1000),maxy=min(maxy,1000),minx=max(minx,-1000),miny=max(miny,-1000);
        int ans=(maxy-miny)*(maxx-minx);
        printf("%d\n",ans);
    }
    return 0;
}



目录
相关文章
|
Java
hdu 2524 矩形A + B
hdu 2524 矩形A + B
36 0
|
Serverless C++
C++/PTA CCircle圆类求圆环面积
定义一个名为CCircle的圆类,要求: 1.其属性数据为圆的半径radius; 2.定义构造函数; 3.成员函数area()计算圆的面积。 4.编写主函数计算一个内径和外径分别为a和b的圆环的面积,其中a和b由键盘输入,π取值为3.14159。
237 0
|
搜索推荐 Java C++
OpenglEs之三角形绘制
Opengl ES连载系列
75 0
牛客网——空心正方形图案
牛客网——空心正方形图案
116 0
HDOJ(HDU) 2091 空心三角形
HDOJ(HDU) 2091 空心三角形
164 0
|
人工智能 算法
洛谷P1387 最大正方形
题目描述 题目链接:https://www.luogu.org/problemnew/show/P1387 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式:  输入文件第一行为两个整数n,m(1
1310 0