http://acm.pku.edu.cn/JudgeOnline/problem?id=1266
题目大意是给定一个圆弧上的3个点（先给2个端点，再给定圆弧中间的一个点），要求出覆盖此圆弧的最小矩形（矩形的4个角坐标必须为整数）
先由给定的3个点可以确定这个圆弧所在圆的圆心的半径，用三角形外接圆圆心公式（好长的公式啊）：
x=mx1+(0.5*((mx2-mx1)*(mx2-mx1)+(my2-my1)*(my2-my1))*(my3-my1)
-0.5*((mx3-mx1)*(mx3-mx1)+(my3-my1)*(my3-my1))*(my2-my1))
/((mx2-mx1)*(my3-my1)-(mx3-mx1)*(my2-my1));
y=my1+(0.5*((mx3-mx1)*(mx3-mx1)+(my3-my1)*(my3-my1))*(mx2-mx1)
-0.5*((mx2-mx1)*(mx2-mx1)+(my2-my1)*(my2-my1))*(mx3-mx1))
/((mx2-mx1)*(my3-my1)-(mx3-mx1)*(my2-my1));
下面求出3个点相对于圆心的偏转角度，有了这个角度之后，我们就可以判断出这段弧是一段优弧还是一段劣弧，进而给定一个角度后，我们就可以判断这个角度的点是否在这段弧上。
然后根据圆的性质很容易求得包围这段圆弧的minx,maxx,miny,maxy
PS:又是可恶的浮点误差WA了我N次，利用floor,ceil函数的时候一定要加上误差控制!!!
floor(x+EPS),ceil(x-EPS)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;#define EPS 1.0e-6
#define pi 3.141592653589793232846double mx1,my1,mx2,my2,mx3,my3;
bool flag;
double a1,a2,a3;
inline
bool zero(double r) {
return fabs(r)<EPS;
}void getcircle(double mx1,double my1,double mx2,double my2,
double mx3,double my3,double &x,double &y) {
x=mx1+(0.5*((mx2-mx1)*(mx2-mx1)+(my2-my1)*(my2-my1))*(my3-my1)
-0.5*((mx3-mx1)*(mx3-mx1)+(my3-my1)*(my3-my1))*(my2-my1))
/((mx2-mx1)*(my3-my1)-(mx3-mx1)*(my2-my1));
y=my1+(0.5*((mx3-mx1)*(mx3-mx1)+(my3-my1)*(my3-my1))*(mx2-mx1)
-0.5*((mx2-mx1)*(mx2-mx1)+(my2-my1)*(my2-my1))*(mx3-mx1))
/((mx2-mx1)*(my3-my1)-(mx3-mx1)*(my2-my1));
}double angle(double x,double y,double mx1,double my1) {
double dx=mx1-x,dy=my1-y;
double theta;
if(zero(dx)) {
if(dy>0) return pi*0.5;
return pi*1.5;
}else{
theta=atan(dy/dx);
if(dx<0) theta+=pi;
else if(dy<0) theta+=2*pi;
}
return theta;
}bool onarc(double angle) {
return ((angle-a1)*(angle-a2)<=0)==flag;
}int main() {
cin>>mx1>>my1>>mx2>>my2>>mx3>>my3;
double x,y;
getcircle(mx1,my1,mx2,my2,mx3,my3,x,y);
double r=sqrt((x-mx1)*(x-mx1)+(y-my1)*(y-my1));
a1=angle(x,y,mx1,my1);
a2=angle(x,y,mx2,my2);
a3=angle(x,y,mx3,my3);
flag=(a3-a1)*(a3-a2)<=0;
int minx,maxx,miny,maxy;
if(onarc(0)) {
maxx=ceil(x+r-EPS);
}else{
maxx=ceil(max(mx1,mx2)-EPS);
}
if(onarc(pi)) {
minx=floor(x-r+EPS);
}else{
minx=floor(min(mx1,mx2)+EPS);
}
if(onarc(pi*0.5)) {
maxy=ceil(y+r-EPS);
}else{
maxy=ceil(max(my1,my2)-EPS);
}
if(onarc(pi*1.5)) {
miny=floor(y-r+EPS);
}else{
miny=floor(min(my1,my2)+EPS);
}
cout<<(((long long)(maxx-minx))*(maxy-miny))<<endl;
return 0;
}
