Ural 1043 Cover the Arc

题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1043

题目大意：一个2000*2000方格坐标，x,y范围都是【-1000,1000】。现在给你一个圆弧，告诉你圆弧的两个端点和任意一个中间点。现在要你算出最小的矩形（长和宽都要为整数，即四个顶点在方格顶点上）来完全覆盖这个圆弧。

算法思路：很明显要算出圆心，这个可以有线段中垂线交求，也可以由方程，只是很麻烦。然后以圆心找出这个圆的左右上下四个极点，判断是否在圆弧上（用叉积即可），与给出的三个点一起维护这段圆弧的四个方向的极大点。然后向上向下取整即可。

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

const double eps = 1e-;

const double INF = 1000000000.00;

struct Point{

    double x,y;

    Point(double x=,double y=): x(x), y(y) {}

};

typedef Point Vector;

Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }

Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }

Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }

bool operator < (const Point& A, const Point& B){

    return A.x < B.x || (A.x == B.x && A.y < B.y);

}

int dcmp(double x){

    if(fabs(x) < eps) return ;

    return x <  ? - : ;

}

bool operator == (const Point& A,const Point& B){

    return dcmp(A.x-B.x) ==  && dcmp(A.y-B.y) == ;

}

double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; }

double Length(Vector A) { return sqrt(Dot(A,A)); }

double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; }

Point read_point()

{

    Point P;

    scanf("%lf %lf",&P.x,&P.y);

    return P;

}

Point normal(Vector A) { return Vector(-A.y,A.x); };

Point GetLineIntersecion(Point P, Vector v,Point Q,Vector w){

    Vector u = P - Q;

    double t = Cross(w,u)/Cross(v,w);

    return P + v*t;

}

void Judge(Point& Pl,Point& Pr,Point& Pu,Point& Pd,Point P){

    if(Pl.x > P.x) Pl = P;

    if(Pr.x < P.x) Pr = P;

    if(Pu.y < P.y) Pu = P;

    if(Pd.y > P.y) Pd = P;

}

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    Point Ps,Pt,Pi;

    Ps = read_point();

    Pt = read_point();

    Pi = read_point();

    Point mid1,mid2,O;

    mid1 = (Ps+Pi)/;

    mid2 = (Pi+Pt)/;

    O = GetLineIntersecion(mid1,normal(Ps-Pi),mid2,normal(Pi-Pt));

    double r = Length(O-Ps);

    Point Pu,Pl,Pr,Pd;

    Pu = Pl = Pr = Pd = Ps;

    Judge(Pl,Pr,Pu,Pd,Pt);

    Judge(Pl,Pr,Pu,Pd,Pi);

    Point P = Point(O.x+r,O.y);

    if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){

        Judge(Pl,Pr,Pu,Pd,P);

    }

    P = Point(O.x-r,O.y);

    if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){

        Judge(Pl,Pr,Pu,Pd,P);

    }

    P = Point(O.x,O.y+r);

    if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){

        Judge(Pl,Pr,Pu,Pd,P);

    }

    P = Point(O.x,O.y-r);

    if(dcmp(Cross(Pt-Ps,Pi-Ps)*Cross(Pt-Ps,P-Ps)) > ){

        Judge(Pl,Pr,Pu,Pd,P);

    }

    int width = ceil(Pu.y-eps) - floor(Pd.y+eps);

    int length = ceil(Pr.x-eps) - floor(Pl.x+eps);

    printf("%d\n",width*length);

}