【UVa 12304】2D Geometry 110 in 1! （计算几何、圆）
程序员文章站
2022-04-02 16:56:00
...
Description
https://vjudge.net/problem/UVA-12304
Solution
都是一些最基本的操作，没什么技术含量，只是代码量有点大，，码了一天，摆上代码吧。
Source
/************************************************
* Happy Spring Festival!
* Au: Hany01
* Date: Feb 11th, 2018
* Prob: UVa12304 2D Geometry 110 in 1!
* Email: [email protected]
************************************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int read()
{
register int _, __; register char c_;
for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
inline void File()
{
#ifdef hany01
freopen("uva12304.in", "r", stdin);
freopen("uva12304.out", "w", stdout);
#endif
}
const double eps = 1e-7, Pi = acos(-1.0);
inline int dcmp(double x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; }
struct Point
{
double x, y;
Point(double x = 0, double y = 0): 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 Vector& A, const Vector& B) {
return !dcmp(A.x - B.x) && !dcmp(A.y - B.y);
}
bool operator < (const Vector& A, const Vector& B) {
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
struct Circle
{
Point O; double r;
Circle(Point O = Point(0, 0), double r = 0): O(O), r(r) {}
Point point(double rad) {
return Point(O.x + cos(rad) * r, O.y + sin(rad) * r);
}
};
Point Mid(Point A, Point B) {
return Point((A.x + B.x) / 2, (A.y + B.y) / 2);
}
double Cross(Point A, Point B) {
return A.x * B.y - A.y * B.x;
}
double Dot(Point A, Point 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));
}
double Angle(Vector A) {
return atan2(A.y, A.x);
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) {
register Vector u = P - Q;
return P + v * (Cross(w, u) / Cross(v, w));
}
Point GetLineProjection(Point P, Point A, Point B) {
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
Vector Rotate(Vector A, double rad) {
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
double DistanceToLine(Point P, Point A, Point B) {
return fabs(Cross(P - A, B - A)) / Length(B - A);
}
inline void Correct(double& x) {
while (dcmp(x) < 0) x += Pi;
while (dcmp(x - Pi) >= 0) x -= Pi;
}
int GetTangents(Circle C, Point P, double* Ans) {
double d = Length(C.O - P);
if (dcmp(d - C.r) < 0) return 0;
double aPC = Angle(P - C.O), theta = acos(C.r / d);
Ans[1] = aPC + theta + Pi / 2, Ans[2] = aPC - theta + Pi / 2;
Correct(Ans[1]), Correct(Ans[2]);
if (!dcmp(Ans[1] - Ans[2])) return 1;
return 2;
}
int GetLineCircleIntersection(Point A, Point B, Circle C, Point& S1, Point& S2) {
double d = DistanceToLine(C.O, A, B);
register int tmp = dcmp(d - C.r);
if (tmp > 0) return 0;
Point P = GetLineProjection(C.O, A, B);
if (!tmp) { S1 = S2 = P; return 1; }
double L = sqrt(C.r * C.r - d * d);
Vector v = (B - A) / Length(B - A);
S1 = P - v * L, S2 = P + v * L;
return 2;
}
int GetCircleIntersection(Circle C1, Circle C2, Point& P1, Point& P2) {
double d = Length(C1.O - C2.O);
if (!dcmp(d)) { if (!dcmp(C1.r - C2.r)) return -1; return 0; }
if (dcmp(C1.r + C2.r - d) < 0 || dcmp(fabs(C1.r - C2.r) - d) > 0) return 0;
double a = Angle(C2.O - C1.O), da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d));
P1 = C1.point(a - da), P2 = C1.point(a + da);
if (P1 == P2) return 1;
return 2;
}
Point move(Point A, double a, double r) { return Point(A.x, A.y + r / cos(a)); }
char Q[40];
int main()
{
File();
while (scanf("%s", Q) != EOF)
{
if (Q[4] == 'u')
{
register Point A, B, C, D, E, vDO, vEO, O;
register double r;
scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);
D = Mid(B, C);
vDO = Vector(B.y - C.y, C.x - B.x),
E = Mid(A, C);
vEO = Vector(A.y - C.y, C.x - A.x);
O = GetLineIntersection(D, vDO, E, vEO), r = Length(O - A);
printf("(%.6lf,%.6lf,%.6lf)\n", O.x, O.y, r);
}
else if (Q[0] == 'I')
{
register Point A, B, C, D, E, vBD, vCE, O;
register double r, ABD, ACE;
scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);
if (dcmp(Cross(B - A, C - A)) < 0) swap(B, C);
ABD = Angle(A - B, C - B) / 2;
ACE = Angle(A - C, B - C) / 2;
vBD = Rotate(C - B, ABD);
vCE = Rotate(B - C, 2 * Pi - ACE);
O = GetLineIntersection(B, vBD, C, vCE);
r = DistanceToLine(O, A, B);
printf("(%.6lf,%.6lf,%.6lf)\n", O.x, O.y, r);
}
else if (Q[0] == 'T')
{
register Circle C;
register Point P;
register double Ans[6];
register int cnt;
scanf("%lf%lf%lf%lf%lf", &C.O.x, &C.O.y, &C.r, &P.x, &P.y);
cnt = GetTangents(C, P, Ans);
if (!cnt) { puts("[]"); continue; }
sort(Ans + 1, Ans + 1 + cnt);
putchar('[');
For(i, 1, cnt - 1) printf("%.6lf,", Ans[i] / Pi * 180);
printf("%.6lf]\n", Ans[cnt] / Pi * 180);
}
else if (Q[13] == 'A')
{
register Point P, A, B, A1, A2, A3;
register double r, d, a;
register Circle C;
register int cntt;
scanf("%lf%lf%lf%lf%lf%lf%lf", &P.x, &P.y, &A.x, &A.y, &B.x, &B.y, &r);
if (!dcmp((d = DistanceToLine(P, A, B)) - r * 2))
{
A1 = GetLineProjection(P, A, B);
printf("[(%lf,%lf)]\n", (A1.x + P.x) / 2, (A1.y + P.y) / 2);
continue;
}
if (dcmp(d - r * 2) > 0) { puts("[]"); continue; }
C = Circle(P, r);
a = Angle(B - A);
if (!(cntt = GetLineCircleIntersection(move(A, a, r), move(B, a, r), C, A1, A2))) {
cntt = GetLineCircleIntersection(move(A, a, -r), move(B, a, -r), C, A1, A2);
}
else if (cntt == 1) GetLineCircleIntersection(move(A, a, -r), move(B, a, -r), C, A2, A3);
if (A2 < A1) swap(A1, A2);
printf("[(%.6lf,%.6lf),(%.6lf,%.6lf)]\n", A1.x, A1.y, A2.x, A2.y);
}
else if (Q[18] == 'L')
{
register Point Ans[6], A1, A2, B1, B2, A1_, VA, B1_, VB;
register double a1, a2, r;
register int cnt = 0;
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf", &A1.x, &A1.y, &A2.x, &A2.y, &B1.x, &B1.y, &B2.x, &B2.y, &r);
a1 = Angle(A2 - A1);
a2 = Angle(B2 - B1);
For(i, -1, 1) if (i) For(j, -1, 1) if (j) {
A1_ = move(A1, a1, r * i);
VA = A2 - A1;
B1_ = move(B1, a2, r * j);
VB = B2 - B1;
Ans[++ cnt] = GetLineIntersection(A1_, VA, B1_, VB);
}
sort(Ans + 1, Ans + 5);
putchar('[');
For(i, 1, 4) printf("(%.6lf,%.6lf)%c", Ans[i].x, Ans[i].y, i == 4 ? ']' : ',');
putchar('\n');
} else if (Q[18] == 'D') {
register Circle C1, C2;
register Point Ans1, Ans2;
register double r;
register int cnt;
scanf("%lf%lf%lf", &C1.O.x, &C1.O.y, &C1.r),
scanf("%lf%lf%lf", &C2.O.x, &C2.O.y, &C2.r);
scanf("%lf", &r), C1.r += r, C2.r += r;
cnt = GetCircleIntersection(C1, C2, Ans1, Ans2);
if (!cnt) puts("[]");
else if (cnt == 1)
printf("[(%lf,%lf)]\n", Ans1.x, Ans1.y);
else
{
if (Ans2 < Ans1) swap(Ans1, Ans2);
printf("[(%lf,%lf),(%lf,%lf)]\n", Ans1.x, Ans1.y, Ans2.x, Ans2.y);
}
}
}
return 0;
}