[计算几何]POJ 1266 三角形的外接圆圆的参数方程

[计算几何]POJ 1266 三角形的外接圆圆的参数方程 - woodfish

woodfish1988 2021-10-26 原文

[计算几何]POJ 1266 三角形的外接圆圆的参数方程

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.141592653589793232846

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