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;
}



目录
相关文章
|
Serverless C++
C++/PTA CCircle圆类求圆环面积
定义一个名为CCircle的圆类,要求: 1.其属性数据为圆的半径radius; 2.定义构造函数; 3.成员函数area()计算圆的面积。 4.编写主函数计算一个内径和外径分别为a和b的圆环的面积,其中a和b由键盘输入,π取值为3.14159。
237 0
洛谷P3829 [SHOI2012]信用卡凸包(点的旋转+凸包)
洛谷P3829 [SHOI2012]信用卡凸包(点的旋转+凸包)
100 0
HDOJ(HDU) 2091 空心三角形
HDOJ(HDU) 2091 空心三角形
168 0
|
人工智能 算法
洛谷P1387 最大正方形
题目描述 题目链接:https://www.luogu.org/problemnew/show/P1387 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式:  输入文件第一行为两个整数n,m(1
1312 0
Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题】
J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 megabytes input:standard input output:standa...
1409 0