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