https://vjudge.net/problem/UVA-12304
大白书 267
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
const double EPS = 1e-10;
const double PI=acos(-1);
using namespace std;
struct Point{
double x;
double y;
Point( double x=0, double y=0):x(x),y(y){}
//void operator<<(Point &A) {cout<<A.x<<' '<<A.y<<endl;}
};
int dcmp(double x) {
if(fabs(x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
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);}
ostream &operator<<(ostream & out,Point & P) { out<<P.x<<' '<<P.y<<endl; return out;}
bool operator< (const Point &A,const Point &B) { return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0); }
bool operator== ( const Point &A,const Point &B) { return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;}
//向量点积
double dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
//向量叉积
double cross(Vector A,Vector B) {return A.x*B.y-B.x*A.y; }
//向量长度
double length(Vector A) { return sqrt(dot(A, A));}
//向量夹角
double angle(Vector A,Vector B) {return acos(dot(A,B)/length(A)/length(B));}
//三角形有向面积的二倍
double area2(Point A,Point B,Point C ) {return cross(B-A, C-A);}
//向量逆时针旋转rad度(弧度)
Vector rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
//计算向量A的单位法向量。左转90°,把长度归一。调用前确保A不是零向量。
Vector normal(Vector A) { double L=length(A);return Vector(-A.y/L,A.x/L);}
/************************************************************************
使用复数类实现点及向量的简单操作
#include <complex>
typedef complex<double> Point;
typedef Point Vector;
double dot(Vector A, Vector B) { return real(conj(A)*B)}
double cross(Vector A, Vector B) { return imag(conj(A)*B);}
Vector rotate(Vector A, double rad) { return A*exp(Point(0, rad)); }
*************************************************************************/
/****************************************************************************
* 用直线上的一点p0和方向向量v表示一条指向。直线上的所有点P满足P = P0+t*v;
* 如果知道直线上的两个点则方向向量为B-A, 所以参数方程为A+(B-A)*t;
* 当t 无限制时, 该参数方程表示直线。
* 当t > 0时, 该参数方程表示射线。
* 当 0 < t < 1时, 该参数方程表示线段。
*****************************************************************************/
//直线交点,须确保两直线有唯一交点。
Point getLineIntersection(Point P,Vector v,Point Q,Vector w)
{
Vector u=P-Q;
double t=cross(w, u)/cross(v,w);
return P+v*t;
}
//点到直线距离
double distanceToLine(Point P,Point A,Point B)
{
Vector v1=P-A; Vector v2=B-A;
return fabs(cross(v1,v2))/length(v2);
}
//点到线段的距离
double distanceToSegment(Point P,Point A,Point B)
{
if(A==B) return length(P-A);
Vector v1=B-A;
Vector v2=P-A;
Vector v3=P-B;
if(dcmp(dot(v1,v2))==-1) return length(v2);
else if(dot(v1,v3)>0) return length(v3);
else return distanceToLine(P, A, B);
}
//点在直线上的投影
Point getLineProjection(Point P,Point A,Point B)
{
Vector v=B-A;
Vector v1=P-A;
double t=dot(v,v1)/dot(v,v);
return A+v*t;
}
//线段相交判定,交点不在一条线段的端点
bool segmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
double c1=cross(b1-a1, a2-a1);
double c2=cross(b2-a1, a2-a1);
double c3=cross(a1-b1, b2-b1);
double c4=cross(a2-b1, b2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0 ;
}
//判断点是否在点段上,不包含端点
bool onSegment(Point P,Point A,Point B)
{
return dcmp(cross(P-A, P-B))==0&&dcmp(dot(P-A,P-B))<0;
}
//计算凸多边形面积
double convexPolygonArea(Point *p, int n) {
double area = 0;
for(int i = 1; i < n-1; i++)
area += cross(p[i] - p[0], p[i+1] - p[0]);
return area/2;
}
//计算多边形的有向面积
double polygonArea(Point *p,int n)
{
double area=0;
for(int i=1;i<n-1;i++)
{
area+=cross(p[i]-p[0], p[i+1]-p[0]);
}
return area/2;
}
/***********************************************************************
* Morley定理:三角形每个内角的三等分线,相交成的三角形是等边三角形。
* 欧拉定理:设平面图的定点数,边数和面数分别为V,E,F。则V+F-E = 2;
************************************************************************/
Point read_point()
{
Point P;
scanf("%lf%lf",&P.x,&P.y);
return P;
}
struct Circle
{
Point c;
double r;
Circle(Point c=Point(0,0), double r=0):c(c),r(r) {}
//通过圆心角确定圆上坐标
Point point( double a)
{
return Point(c.x+r*cos(a),c.y+r*sin(a));
}
};
struct Line
{
Point p;
Vector v;
double ang;
Line(Point p=Point(0,0),Vector v=Vector(0,1)):p(p),v(v) {}
Point point( double t)
{
return Point(p+v*t);
}
bool operator < (const Line& L) const {
return ang < L.ang;
}
};
//直线和圆的交点,返回交点个数,结果存在sol中。
//该代码没有清空sol。
int getLineCircleIntersection(Line L,Circle cir, double &t1, double &t2,vector<Point> &sol)
{
double a=L.v.x;
double b=L.p.x-cir.c.x;
double c=L.v.y;
double d=L.p.y-cir.c.y;
double e=a*a+c*c;
double f=2*(a*b+c*d);
double g=b*b+d*d-cir.r*cir.r;
double delta=f*f-4*e*g;
if(dcmp(delta)<0) return 0;
if(dcmp(delta)==0)
{
t1=t2=-f/(2*e);
sol.push_back(L.point(t1));
return 1;
}
else
{
t1=(-f-sqrt(delta))/(2*e);
t2=(-f+sqrt(delta))/(2*e);
sol.push_back(L.point(t1));
sol.push_back(L.point(t2));
return 2;
}
}
// 向量极角公式
double angle(Vector v) {return atan2(v.y,v.x);}
//两圆相交
int getCircleCircleIntersection(Circle C1,Circle C2,vector<Point> &sol)
{
double d=length(C1.c-C2.c);
if(dcmp(d)==0)
{
if(dcmp(C1.r-C2.r)==0) return -1; // 重合
else return 0; // 内含 0 个公共点
}
if(dcmp(C1.r+C2.r-d)<0) return 0; // 外离
if(dcmp(fabs(C1.r-C2.r)-d)>0) return 0; // 内含
double a=angle(C2.c-C1.c);
double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));
Point p1=C1.point(a-da);
Point p2=C1.point(a+da);
sol.push_back(p1);
if(p1==p2) return 1; // 相切
else
{
sol.push_back(p2);
return 2;
}
}
//过定点做圆的切线
//过点p做圆C的切线,返回切线个数。v[i]表示第i条切线
int getTangents(Point p,Circle cir,Vector *v)
{
Vector u=cir.c-p;
double dist=length(u);
if(dcmp(dist-cir.r)<0) return 0;
else if(dcmp(dist-cir.r)==0)
{
v[0]=rotate(u,PI/2);
return 1;
}
else
{
double ang=asin(cir.r/dist);
v[0]=rotate(u,-ang);
v[1]=rotate(u,+ang);
return 2;
}
}
//两圆的公切线
//返回切线的个数,-1表示有无数条公切线。
//a[i], b[i] 表示第i条切线在圆A,圆B上的切点
int getTangents(Circle A, Circle B, Point *a, Point *b) {
int cnt = 0;
if(A.r < B.r) {
swap(A, B); swap(a, b);
}
int d2 = (A.c.x - B.c.x)*(A.c.x - B.c.x) + (A.c.y - B.c.y)*(A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff*rdiff) return 0; //内含
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == 0 && A.r == B.r) return -1; //无限多条切线
if(d2 == rdiff*rdiff) { //内切一条切线
a[cnt] = A.point(base);
b[cnt] = B.point(base);
cnt++;
return 1;
}
//有外共切线
double ang = acos((A.r-B.r) / sqrt(d2));
a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang); cnt++;
a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang); cnt++;
if(d2 == rsum*rsum) { //一条公切线
a[cnt] = A.point(base);
b[cnt] = B.point(PI+base);
cnt++;
} else if(d2 > rsum*rsum) { //两条公切线
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base+ang); b[cnt] = B.point(PI+base+ang); cnt++;
a[cnt] = A.point(base-ang); b[cnt] = B.point(PI+base-ang); cnt++;
}
return cnt;
}
typedef vector<Point> Polygon;
//点在多边形内的判定
int isPointInPolygon(Point p, Polygon poly) {
int wn = 0;
int n = poly.size();
for(int i = 0; i < n; i++) {
if(onSegment(p, poly[i], poly[(i+1)%n])) return -1; //在边界上
int k = dcmp(cross(poly[(i+1)%n]-poly[i], p-poly[i]));
int d1 = dcmp(poly[i].y - p.y);
int d2 = dcmp(poly[(i+1)%n].y - p.y);
if(k > 0 && d1 <= 0 && d2 > 0) wn++;
if(k < 0 && d2 <= 0 && d1 > 0) wn++;
}
if(wn != 0) return 1; //内部
return 0; //外部
}
//凸包
/***************************************************************
* 输入点数组p, 个数为p, 输出点数组ch。 返回凸包顶点数
* 不希望凸包的边上有输入点,把两个<= 改成 <
* 高精度要求时建议用dcmp比较
* 输入点不能有重复点。函数执行完以后输入点的顺序被破坏
****************************************************************/
int convexHull(Point *p, int n, Point* ch) {
sort(p, p+n); //先比较x坐标,再比较y坐标
int m = 0;
for(int i = 0; i < n; i++) {
while(m > 1 && cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-2; i >= 0; i++) {
while(m > k && cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
if(n > 1) m--;
return m;
}
//用有向直线A->B切割多边形poly, 返回“左侧”。 如果退化,可能会返回一个单点或者线段
//复杂度O(n2);
Polygon cutPolygon(Polygon poly, Point A, Point B) {
Polygon newpoly;
int n = poly.size();
for(int i = 0; i < n; i++) {
Point C = poly[i];
Point D = poly[(i+1)%n];
if(dcmp(cross(B-A, C-A)) >= 0) newpoly.push_back(C);
if(dcmp(cross(B-A, C-D)) != 0) {
Point ip = getLineIntersection(A, B-A, C, D-C);
if(onSegment(ip, C, D)) newpoly.push_back(ip);
}
}
return newpoly;
}
//半平面交
//点p再有向直线L的左边。(线上不算)
bool onLeft(Line L, Point p) {
return cross(L.v, p-L.p) > 0;
}
//两直线交点,假定交点唯一存在
Point getIntersection(Line a, Line b) {
Vector u = a.p - b.p;
double t = cross(b.v, u) / cross(a.v, b.v);
return a.p+a.v*t;
}
int halfplaneIntersection(Line* L, int n, Point* poly) {
sort(L, L+n); //按极角排序
int first, last; //双端队列的第一个元素和最后一个元素
Point *p = new Point[n]; //p[i]为q[i]和q[i+1]的交点
Line *q = new Line[n]; //双端队列
q[first = last = 0] = L[0]; //队列初始化为只有一个半平面L[0]
for(int i = 0; i < n; i++) {
while(first < last && !onLeft(L[i], p[last-1])) last--;
while(first < last && !onLeft(L[i], p[first])) first++;
q[++last] = L[i];
if(fabs(cross(q[last].v, q[last-1].v)) < EPS) {
last--;
if(onLeft(q[last], L[i].p)) q[last] = L[i];
}
if(first < last) p[last-1] = getIntersection(q[last-1], q[last]);
}
while(first < last && !onLeft(q[first], p[last-1])) last--;
//删除无用平面
if(last-first <= 1) return 0; //空集
p[last] = getIntersection(q[last], q[first]);
//从deque复制到输出中
int m = 0;
for(int i = first; i <= last; i++) poly[m++] = p[i];
return m;
}
// 求内切圆坐标
Circle inscribledCircle(Point p1,Point p2,Point p3)
{
double a=length(p2-p3);
double b=length(p3-p1);
double c=length(p1-p2);
Point I=(p1*a+p2*b+p3*c)/(a+b+c);
return Circle(I,distanceToLine(I, p1, p2));
}
//求外接圆坐标
Circle circumscribedCircle(Point p1,Point p2,Point p3)
{
double Bx=p2.x-p1.x,By=p2.y-p1.y;
double Cx=p3.x-p1.x,Cy=p3.y-p1.y;
double D=2*(Bx*Cy-By*Cx);
double cx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
double cy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;
Point p=Point(cx,cy);
return Circle(p,length(p-p1));
}
int main()
{
char str[50];
Point A,B,C;
while(scanf("%s",str)!=EOF)
{
if(!strcmp(str,"CircumscribedCircle"))
{
A=read_point();
B=read_point();
C=read_point();
Circle cir=circumscribedCircle(A, B, C);
printf("(%.6f,%.6f,%.6f)\n",cir.c.x,cir.c.y,cir.r);
}
else if(!strcmp(str,"InscribedCircle"))
{
A=read_point();
B=read_point();
C=read_point();
Circle cir=inscribledCircle(A, B, C);
printf("(%.6f,%.6f,%.6f)\n",cir.c.x,cir.c.y,cir.r);
}
else if(!strcmp(str,"TangentLineThroughPoint"))
{
Circle cir;
cir.c=read_point();
scanf("%lf",&cir.r);
Point p=read_point();
Vector vec[2];
double val[2];
int ans=getTangents(p, cir,vec);
if(ans)
{
for(int i=0;i<ans;i++) // atan2 返回的极角范围是-PI到PI
{
if(dcmp(angle(vec[i]))<0)
{
val[i]=(angle(vec[i])+PI)/PI*180;
}
else val[i]=angle(vec[i])/PI*180;
if(dcmp(val[i]-180.0)==0) val[i]=0.0;
}
sort(val,val+ans);
printf("[");
for(int i=0;i<ans-1;i++)
printf("%.6f,",val[i]);
printf("%.6f]\n",val[ans-1]);
}
else
{
printf("[]\n");
}
}
else if(!strcmp(str,"CircleThroughAPointAndTangentToALineWithRadius"))
{
Point p=read_point();
Point A=read_point();
Point B=read_point();
double r;
scanf("%lf",&r);
Vector dir=B-A;
Vector v1=normal(dir);
Vector v2=rotate(v1, PI);
Point p1=A+v1*r;
Point p2=A+v2*r;
Line L1=Line(p1,dir);
Line L2=Line(p2,dir);
vector<Point> sol;
double t1=0,t2=0;
int ans=getLineCircleIntersection(L1, Circle(p,r), t1, t2,sol);
ans+=getLineCircleIntersection(L2, Circle(p,r), t1, t2, sol);
if(!ans)
{
printf("[]\n");
}
else
{
sort(sol.begin(),sol.end());
printf("[");
for(int i=0;i<ans-1;i++)
printf("(%.6f,%.6f),",sol[i].x,sol[i].y);
printf("(%.6f,%.6f)]\n",sol[ans-1].x,sol[ans-1].y);
}
}
else if(!strcmp(str,"CircleTangentToTwoLinesWithRadius"))
{
Point A1=read_point(),B1=read_point(),A2=read_point(),B2=read_point();
double r;
scanf("%lf",&r);
Vector v1=B1-A1;
Vector v2=B2-A2;
Vector normal_1_1=normal(v1);
Vector normal_1_2=rotate(normal_1_1, PI);
Point p1=A1+normal_1_1*r;
Point p2=A1+normal_1_2*r;
Vector normal_2_1=normal(v2);
Vector normal_2_2=rotate(normal_2_1, PI);
Point p3=A2+normal_2_1*r;
Point p4=A2+normal_2_2*r;
vector<Point> ans;
ans.push_back(getLineIntersection(p1, v1, p3, v2));
ans.push_back(getLineIntersection(p1, v1, p4, v2));
ans.push_back(getLineIntersection(p2, v1, p3, v2));
ans.push_back(getLineIntersection(p2, v1, p4, v2));
sort(ans.begin(),ans.end());
printf("[");
for(int i=0;i<3;i++)
printf("(%.6f,%.6f),",ans[i].x,ans[i].y);
printf("(%.6f,%.6f)]\n",ans[3].x,ans[3].y);
}
else if(!strcmp(str,"CircleTangentToTwoDisjointCirclesWithRadius"))
{
Circle A,B;
A.c=read_point();
scanf("%lf",&A.r);
B.c=read_point();
scanf("%lf",&B.r);
double r;
scanf("%lf",&r);
vector<Point> ans;
int cnt=getCircleCircleIntersection(Circle(A.c,A.r+r), Circle(B.c,B.r+r), ans);
if(!cnt)
{
printf("[]\n");
}
else
{
sort(ans.begin(),ans.end());
printf("[");
for(int i=0;i<cnt-1;i++)
printf("(%.6f,%.6f),",ans[i].x,ans[i].y);
printf("(%.6f,%.6f)]\n",ans[cnt-1].x,ans[cnt-1].y);
}
}
}
}