UVA12304 2D Geometry 110 in 1!
计算几何
基础函数都在里面啦！
\(Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<map>
#define db double
using namespace std;
map<string,int>opt;
const db eps=1e-7;
const db Pi=acos(-1.0);
db a,b,c,d,e,f,r,r1,r2;
int q0=0,Q0=0;
db q[15];
string s;
// 等于
bool Equ(db x,db y)
{
return fabs(x-y)<eps;
}
// 不等于
bool NEqu(db x,db y)
{
return fabs(x-y)>=eps;
}
// 小于
bool Sm(db x,db y)
{
return y-x>eps;
}
// 小于等于
bool Le(db x,db y)
{
return y-x>-eps;
}
// 大于
bool Bg(db x,db y)
{
return x-y>eps;
}
// 大于等于
bool Ge(db x,db y)
{
return x-y>-eps;
}
// 角度转正数
db Posi(db x)
{
if (x>=0)
return x-(int)(x/360.0)*360.0; else
if (Equ((int)(x/360.0)*360.0,x))
return 0.0; else
return x+((int)(-x/360.0)+1)*360.0;
}
// 角度转0~180度（不包含180度）
db Stan(db x)
{
x=Posi(x);
if (Ge(x,180.0))
x-=180.0;
return x;
}
// 弧度转角度
db Turn(db x)
{
return Posi(x/Pi*180.0);
}
// 点（向量表示）
struct Point
{
db x,y;
Point (db xx=0.0,db yy=0.0)
{
x=xx,y=yy;
}
void read()
{
scanf("%lf%lf",&x,&y);
}
void print()
{
printf("%.5lf %.5lf\n",x,y);
}
bool operator < (const Point &A) const
{
if (!Equ(x,A.x))
return Sm(x,A.x);
return Sm(y,A.y);
}
}A,B,C,D,E,F,G,H,I,J,K,O,O1,O2,Q[15];
// 加法
Point operator + (Point A,Point B)
{
return Point(A.x+B.x,A.y+B.y);
}
// 减法
Point operator - (Point A,Point B)
{
return Point(A.x-B.x,A.y-B.y);
}
// 数乘
Point operator * (Point A,db B)
{
return Point(B*A.x,B*A.y);
}
Point operator * (db B,Point A)
{
return Point(B*A.x,B*A.y);
}
// 数除
Point operator / (Point A,db B)
{
return Point(A.x/B,A.y/B);
}
Point operator / (db B,Point A)
{
return Point(A.x/B,A.y/B);
}
// 点积
db operator * (Point A,Point B)
{
return A.x*B.x+A.y*B.y;
}
// 叉积
db operator ^ (Point A,Point B)
{
return A.x*B.y-A.y*B.x;
}
// 等于
bool operator == (Point A,Point B)
{
return Equ(A.x,B.x) && Equ(A.y,B.y);
}
// 不等于
bool operator != (Point A,Point B)
{
return !Equ(A.x,B.x) || !Equ(A.y,B.y);
}
// 模长
db Len(Point A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
// 中点
Point Mid(Point A)
{
return Point(0.5*A.x,0.5*A.y);
}
// 垂直向量
Point Verc(Point A)
{
return Point(-A.y,A.x);
}
// 两点间距离
db Dis(Point A,Point B)
{
return Len(A-B);
}
// 两点中点
Point Mid(Point A,Point B)
{
return Point(0.5*(A.x+B.x),0.5*(A.y+B.y));
}
// 极角
db Angle(Point A)
{
return atan2(A.y,A.x);
}
// 三角形角度（c边所对的角）
db Angle(db a,db b,db c)
{
return acos((a*a+b*b-c*c)/(2.0*a*b));
}
// 旋转（将点A绕原点旋转角度k）
Point Rot(Point A,db k)
{
db s=sin(k),c=cos(k);
return Point(A.x*c-A.y*s,A.x*s+A.y*c);
}
// 旋转（将点A绕点B旋转角度k）
Point Rot(Point A,Point B,db k)
{
Point C=A-B;
db s=sin(k),c=cos(k);
return Point(B.x+C.x*c-C.y*s,B.y+C.x*s+C.y*c);
}
// 做点A关于点B的对称点
Point Sym(Point A,Point B)
{
return Point(2.0*B.x-A.x,2.0*B.y-A.y);
}
// 直线
struct Line
{
// P表示直线上一点，t表示方向向量
// L=P+kt
Point P,t;
Line (Point A=Point(0.0,0.0),Point B=Point(0.0,0.0))
{
P=A,t=B;
}
void print()
{
printf("P: %.5lf %.5lf\n",P.x,P.y);
printf("t: %.5lf %.5lf\n",t.x,t.y);
}
}L1,L2,L3,L4,L5,L6,L7,L8,L9,L10;
// 把两点转为直线
Line ToLine(Point A,Point B)
{
return Line(A,B-A);
}
// 将指定的k值代入直线
Point Get(Line A,db k)
{
return A.P+k*A.t;
}
// 得到直线上随机一点
Point Get_Rand(Line A)
{
return A.P+19.19191919*A.t;
}
// 求中垂线
Line Median (Point A,Point B)
{
return Line(Mid(A,B),Verc(B-A));
}
// 做平行线
Line Para(Point A,Line L)
{
return Line(A,L.t);
}
// 做垂线
Line Verc(Point A,Line L)
{
return Line(A,Verc(L.t));
}
// 求直线交点
Point Cross (Line L1,Line L2)
{
Point A=Get(L1,1.0),B=Get(L1,-1.0);
Point C=Get(L2,1.0),D=Get(L2,-1.0);
db S1=(C-A)^(C-B);
db S2=(D-A)^(D-B);
Point del=D-C;
return Point(C.x+del.x*S1/(S1-S2),C.y+del.y*S1/(S1-S2));
}
// 点到直线垂足
Point Pedal(Point A,Line L)
{
Line L1=Verc(A,L);
return Cross(L1,L);
}
// 判断是否在直线上
bool OnLine(Point C,Line L)
{
Point A=Get(L,1.0),B=Get(L,-1.0);
return Equ((C-A)^(C-B),0.0);
}
// 截取射线AB上AC=k
Point Cut(Point A,Point B,db k)
{
Point del=B-A;
del=(del/Len(del))*k;
return A+del;
}
// 直线与x轴夹角
db Angle(Line A)
{
return Angle(A.t);
}
// 圆（圆心O、半径r）
struct Circle
{
Point O;
db r;
Circle (Point A=Point(0.0,0.0),db k=0.0)
{
O=A,r=k;
}
void read()
{
scanf("%lf%lf%lf",&O.x,&O.y,&r);
}
}C1,C2,C3,C4,C5,C6;
int main()
{
opt["CircumscribedCircle"]=1;
opt["InscribedCircle"]=2;
opt["TangentLineThroughPoint"]=3;
opt["CircleThroughAPointAndTangentToALineWithRadius"]=4;
opt["CircleTangentToTwoLinesWithRadius"]=5;
opt["CircleTangentToTwoDisjointCirclesWithRadius"]=6;
while (cin >> s)
{
switch (opt[s])
{
case 1:
A.read(),B.read(),C.read();
L1=Median(A,B),L2=Median(A,C);
D=Cross(L1,L2);
printf("(%.6lf,%.6lf,%.6lf)\n",D.x,D.y,Dis(A,D));
break;
case 2:
A.read(),B.read(),C.read();
a=Dis(B,C),b=Dis(A,C),c=Dis(A,B);
D=B+(C-B)*(c/(c+b)),E=A+(C-A)*(c/(a+c));
L1=ToLine(A,D),L2=ToLine(B,E);
F=Cross(L1,L2);
L3=ToLine(A,C);
G=Pedal(F,ToLine(A,C));
printf("(%.6lf,%.6lf,%.6lf)\n",F.x,F.y,Dis(F,G));
break;
case 3:
C1.read(),A.read();
q0=0;
O=C1.O,a=Dis(O,A),b=C1.r;
if (Sm(a,b))
q0=0; else
{
c=sqrt(a*a-b*b);
d=atan(c/b);
B=Rot(A,O,d),C=Rot(A,O,-d);
D=Cut(O,B,b),E=Cut(O,C,b);
q[++q0]=Angle(ToLine(A,D));
if (D!=E)
q[++q0]=Angle(ToLine(A,E));
}
for (int i=1;i<=q0;++i)
q[i]=Stan(Turn(q[i]));
sort(q+1,q+q0+1);
if (!q0)
puts("[]"); else
if (q0==1)
printf("[%.6lf]\n",q[1]); else
printf("[%.6lf,%.6lf]\n",q[1],q[2]);
break;
case 4:
A.read(),B.read(),C.read(),scanf("%lf",&r);
Q0=0;
L1=ToLine(B,C);
D=Pedal(A,L1);
a=Dis(A,D);
if (Equ(a,r+r))
Q[++Q0]=Mid(A,D); else
if (!Bg(a,r+r))
{
if (OnLine(A,L1))
{
L2=Verc(A,L1);
E=Get_Rand(L2);
G=Cut(A,E,r),H=Cut(A,E,-r);
Q[++Q0]=G,Q[++Q0]=H;
} else
{
b=sqrt(r*r-(r-a)*(r-a));
if (B==D)
swap(B,C);
E=Cut(D,B,b),F=Cut(D,B,-b);
L2=Verc(E,L1),L3=Verc(F,L1);
G=Pedal(A,L2),H=Pedal(A,L3);
I=Cut(E,G,r),J=Cut(F,H,r);
Q[++Q0]=I,Q[++Q0]=J;
}
}
sort(Q+1,Q+Q0+1);
if (Q0==0)
puts("[]"); else
{
printf("[(%.6lf,%.6lf)",Q[1].x,Q[1].y);
for (int i=2;i<=Q0;++i)
printf(",(%.6lf,%.6lf)",Q[i].x,Q[i].y);
putchar(']'),putchar('\n');
}
break;
case 5:
A.read(),B.read(),C.read(),D.read(),scanf("%lf",&r);
Q0=0;
L1=ToLine(A,B),L2=ToLine(C,D);
E=Cross(L1,L2);
L3=Verc(E,L1),L4=Verc(E,L2);
F=Get_Rand(L3);
H=Cut(E,F,r),I=Cut(E,F,-r);
L5=Para(H,L1),L6=Para(I,L1);
F=Get_Rand(L4);
H=Cut(E,F,r),I=Cut(E,F,-r);
L7=Para(H,L2),L8=Para(I,L2);
Q[++Q0]=Cross(L5,L7),Q[++Q0]=Cross(L5,L8);
Q[++Q0]=Cross(L6,L7),Q[++Q0]=Cross(L6,L8);
sort(Q+1,Q+Q0+1);
if (Q0==0)
puts("[]"); else
{
printf("[(%.6lf,%.6lf)",Q[1].x,Q[1].y);
for (int i=2;i<=Q0;++i)
printf(",(%.6lf,%.6lf)",Q[i].x,Q[i].y);
putchar(']'),putchar('\n');
}
break;
case 6:
C1.read(),C2.read(),scanf("%lf",&r);
if (C1.r<C2.r)
swap(C1,C2);
Q0=0;
O1=C1.O,O2=C2.O,r1=C1.r,r2=C2.r;
a=Dis(O1,O2);
r1+=r,r2+=r;
if (Equ(a,r1+r2))
Q[++Q0]=Cut(O1,O2,r1); else
if (!Bg(a,r1+r2))
{
b=r1*((a*a+r1*r1-r2*r2)/(2.0*a*r1));
c=sqrt(r1*r1-b*b);
A=Cut(O1,O2,b);
L3=ToLine(O1,O2);
L4=Verc(A,L3);
B=Get_Rand(L4);
Q[++Q0]=Cut(A,B,c);
Q[++Q0]=Cut(A,B,-c);
}
sort(Q+1,Q+Q0+1);
if (Q0==0)
puts("[]"); else
{
printf("[(%.6lf,%.6lf)",Q[1].x,Q[1].y);
for (int i=2;i<=Q0;++i)
printf(",(%.6lf,%.6lf)",Q[i].x,Q[i].y);
putchar(']'),putchar('\n');
}
break;
default:
puts("Error");
break;
}
}
return 0;
}