840
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;
}
最後更新：2017-04-03 15:22:09