UVa12304（计算几何中圆的基本操作）

断断续续写了250多行的模拟，其间被其他事情打扰，总共花了一天才AC吧~

这道题目再次让我明白，有些事情看起来很难，实际上并没有我们想象中的那么难。当然了我主要指的不是这个题的难度……

也是初学计算几何，然后居然胆大妄为地不用刘汝佳的思路去实现这些个功能，其中有三个功能是我用自己的思路实现的吧（瞎暴力），最后果然也是自己写的出锅了。

当一个贼长的模拟题交上去一发WA时，我是欲哭无泪的……这让我怎么debug……只好不断安慰自己要用计算几何题去练习耐心。

只是没想到在不断的固执与冷静的试探之下，不到一个晚上就成功了，当然了，对拍拍出来的呗……

我的主要错误在于在我自己的实现思路里，旋转向量时应该顺时针还是逆时针是取决于输入的，而我粗暴地“一视同仁”了。还好后来发现不难改，加个正负1去control就好了~

自己的辣鸡代码贴一贴留着自己看，难得写这么长：

 #include <bits/stdc++.h>

 using namespace std;

 struct Point

 {

     double x, y;

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

 };

 typedef Point Vector;

 const double PI = acos(-1.0);

 int dcmp(double x)

 {

     if (fabs(x) < 1e-)    return ;

     else    return x <  ? - : ;

 }

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

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

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

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

 bool operator < (const Point &A, const Point &B) { return dcmp(A.x - B.x) <  || (dcmp(A.x - B.x) ==  && dcmp(A.y - B.y) < ); }

 bool operator == (const Point &A, const Point &B) { return dcmp(A.x - B.x) ==  && dcmp(A.y - B.y) == ; }

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

 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 Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }

 Vector Normal(Vector A) { double L = Length(A); return Vector(-A.y / L, A.x / L); }

 Vector Rotate(Vector A, double rad) { return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); }

 Point Get_Line_Intersect(Point P, Vector v, Point Q, Vector w)

 {

     Point u = P - Q;

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

     return P + v*t;

 }

 double Distance_to_Line(Point P, Point A, Point B)

 {

     Vector v1 = P - A, v2 = B - A;

     return fabs(Cross(v1, v2) / Length(v2));

 }

 struct Circle

 {

     Point c;

     double r;

     // Circle(Point a = (0, 0), double x = 0):c(a), r(x){}

     Point point(double seta) { return Point(c.x + cos(seta)*r, c.y + sin(seta)*r); }

 };

 struct Line

 {

     Point p;

     Vector v;

     Line(Point p, Vector v):p(p), v(v) { }

     Point point(double t) { return p + v*t; }

     Line move(double d) { return Line(p + Normal(v)*d, v); }

 };

 double formattedAngle(Vector A)

 {

     double a = atan2(A.y, A.x) / PI * ;

     if (dcmp(a) < )    a += ;

     if (dcmp(a - ) >= )    a -= ;

     return a;

 }

 int getTangents(Point P, Circle C, vector<double> &v)

 {

     Vector u = C.c - P;

     double d = Length(u);

     if (dcmp(d - C.r) < )    return ;

     else if (dcmp(d - C.r) == )

     {

         v.push_back(formattedAngle(Rotate(u, PI/)));

         return ;

     }

     else

     {

         double a = asin(C.r / d);

         v.push_back(formattedAngle(Rotate(u, a)));

         v.push_back(formattedAngle(Rotate(u, -a)));

         return ;

     }

 }

 void get_Line_Circle_Intersection(Line L, Circle C, vector<Point> &ans)

 {

     double t1, t2;

     double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;

     double e = a*a + c*c, f = *(a*b + c*d), g = b*b + d*d - C.r*C.r;

     double delta = f*f - *e*g;

     if (dcmp(delta) < )    return;

     else if (dcmp(delta) == )

     {

         t1 = t2 = -f//e;

         ans.push_back(L.point(t1));

     }

     else

     {

         t1 = (-f + sqrt(delta)) /  / e;

         t2 = (-f - sqrt(delta)) /  / e;

         ans.push_back(L.point(t1)), ans.push_back(L.point(t2));

     }

 }

 inline double angle(Vector A) { return atan2(A.y, A.x); }

 int get_Circle_Circle_Intersection(Circle C1, Circle C2, vector<Point> &v)

 {

     double d = Length(C1.c - C2.c);

     if (dcmp(d) == )

     {

         if (dcmp(C1.r - C2.r) == )    return -;

         return ;

     }

     if (dcmp(C1.r + C2.r - d) < )    return ;

     if (dcmp(fabs(C1.r - C2.r) - d) > )    return ;

     double a = angle(C2.c - C1.c);

     double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (*C1.r*d));

     Point p1 = C1.point(a - da), p2 = C1.point(a + da);

     v.push_back(p1);

     if (p1 == p2)    return ;

     v.push_back(p2);

     return ;

 }

 void CircumscribedCircle()

 {

     Point P[];

     for (int i = ; i < ; i++)    scanf("%lf%lf", &P[i].x, &P[i].y);

     Point c = Get_Line_Intersect((P[] + P[])/, Rotate(P[] - P[], PI/), (P[] + P[])/, Rotate(P[] - P[], -PI/));

     printf("(%.6lf,%.6lf,%.6lf)\n", c.x, c.y, Length(c - P[]));

 }

 void InscribedCircle()

 {

     Point P[];

     for (int i = ; i < ; i++)    scanf("%lf%lf", &P[i].x, &P[i].y);

     Vector v1 = Rotate(P[] - P[], (Cross(P[] - P[], P[] - P[]) >  ? - : ) * Angle(P[]-P[], P[]-P[]) / );

     Vector v2 = Rotate(P[] - P[], (Cross(P[] - P[], P[] - P[]) >  ? - : ) * Angle(P[]-P[], P[]-P[]) / );

     Point c = Get_Line_Intersect(P[], v1, P[], v2);

     printf("(%.6lf,%.6lf,%.6lf)\n", c.x, c.y, Distance_to_Line(c, P[], P[]));

 }

 void TangentLineThroughPoint()

 {

     Circle C;

     Point P;

     vector<double> v;

     scanf("%lf%lf%lf", &C.c.x, &C.c.y, &C.r);

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

     printf("[");

     if (getTangents(P, C, v))    sort(v.begin(), v.end()), printf("%.6lf", v[]);

     if (v.size() == )    printf(",%.6lf", v[]);

     printf("]\n");

 }

 void CircleThroughAPointAndTangentToALineWithRadius()

 {

     Circle P;

     Point A, B;

     scanf("%lf%lf%lf%lf%lf%lf%lf", &P.c.x, &P.c.y, &A.x, &A.y, &B.x, &B.y, &P.r);

     Line original(A, B - A);

     vector<Point> v;

     get_Line_Circle_Intersection(original.move(P.r), P, v);

     get_Line_Circle_Intersection(original.move(-P.r), P, v);

     sort(v.begin(), v.end());

     printf("[");

     if (v.size())    printf("(%.6lf,%.6lf)", v[].x, v[].y);

     for (int i = ; i < v.size(); i++)    printf(",(%.6lf,%.6lf)", v[i].x, v[i].y);

     printf("]\n");

 }

 inline Point e_to_go(Vector A, double len) { return A / Length(A) * len; }

 void CircleTangentToTwoLinesWithRadius()

 {

     Point A, B, C ,D;

     double r;

     scanf("%lf%lf %lf%lf %lf%lf %lf%lf %lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y, &D.x, &D.y, &r);

     vector<Point> v;

     int control = Cross(B - A, D - C) <  ? - : ;

     Point P = Get_Line_Intersect(A, B-A, C, D-C);

     double seta = Angle(B - A, D - C)/;

     Vector v1 = Rotate(B - A, control*seta);

     Vector v2 = Rotate(B - A, -control*(PI/ - seta));

     v.push_back(P + e_to_go(v1, r/sin(seta)));

     v.push_back(P - e_to_go(v1, r/sin(seta)));

     v.push_back(P + e_to_go(v2, r/cos(seta)));

     v.push_back(P - e_to_go(v2, r/cos(seta)));

     sort(v.begin(), v.end());

     for (int i = ; i < v.size(); i++)

         printf("%c(%.6lf,%.6lf)", ",["[i == ], v[i].x, v[i].y);

     printf("]\n");

 }

 void CircleTangentToTwoDisjointCirclesWithRadius()

 {

     Circle C1, C2;

     double r;

     scanf("%lf%lf%lf %lf%lf%lf %lf", &C1.c.x, &C1.c.y, &C1.r, &C2.c.x, &C2.c.y, &C2.r, &r);

     C1.r += r, C2.r += r;

     vector<Point> v;

     get_Circle_Circle_Intersection(C1, C2, v);

     sort(v.begin(), v.end());

     if (!v.size())    printf("[");

     for (int i = ; i < v.size(); i++)

         printf("%c(%.6lf,%.6lf)", ",["[i == ], v[i].x, v[i].y);

     printf("]\n");

 }

 int main()

 {

     string s;

     while (cin >> s)

     {

         if (s.length() < )    InscribedCircle();

         else

         {

             switch(s[])

             {

                 case 'e':

                     CircumscribedCircle(); break;

                 case 'P':

                     TangentLineThroughPoint(); break;

                 case 't':

                     CircleThroughAPointAndTangentToALineWithRadius(); break;

                 case 'L':

                     CircleTangentToTwoLinesWithRadius(); break;

                 case 'D':

                     CircleTangentToTwoDisjointCirclesWithRadius(); break;

                 default : break;

             }

         }

     }

     return ;

 }