首页 > 代码库 > UVa 12304 (6个二维几何问题合集) 2D Geometry 110 in 1!
UVa 12304 (6个二维几何问题合集) 2D Geometry 110 in 1!
这个题能1A纯属运气，要是WA掉，可真不知道该怎么去调了。
题意：
这是完全独立的6个子问题。代码中是根据字符串的长度来区分问题编号的。
- 给出三角形三点坐标，求外接圆圆心和半径。
- 给出三角形三点坐标，求内切圆圆心和半径。
- 给出一个圆和一个定点，求过定点作圆的所有切线的倾角(0≤a＜180°)
- 给出一个点和一条直线，求一个半径为r的过该点且与该直线相切的圆。
- 给出两条相交直线，求所有半径为r且与两直线都相切的圆。
- 给出两个相离的圆，求半径为r且与两圆都相切的圆。
分析：
- 写出三角形两边的垂直平分线的一般方程(注意去掉分母，避免直线是水平或垂直的特殊情况)，然后联立求解即可。
- 有一个很简洁的三角形内心坐标公式(证明有点复杂，可用向量来证，其中多次用到角平分线定理)，公式详见代码。
- 分点在圆内，圆上，圆外三种情况，注意最终结果的范围。
- 到定点距离为r的轨迹是个圆，与直线相切的圆心的轨迹是两条平行直线。最终转化为求圆与两条平行线的交点。
- 我开始用的方法是求出圆心到两直线交点的距离，以及与其中一条直线的夹角，依次旋转三个90°即可得到另外三个点。但是对比正确结果，误差居然达到了个位(如果代码没有错的话)！后来参考了lrj的思路，就是讲两直线分别向两侧平移r距离，这样得到的四条直线两两相交得到的四个交点就是所求。
- 看起来有点复杂，仔细分析，半径为r与圆外切的圆心的轨迹还是个圆。因此问题转化为求半径扩大以后的两圆的交点。
体会：
- (Point)(x, y)是强制类型转换，Point(x, y)才是调用构造函数。前者只会将x的值复制，y的值则是默认值0.
- 计算的中间步骤越多，误差越大，最好能优化算法，或者调整EPS的大小。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 #include <cmath> 7 #include <vector> 8 using namespace std; 9 10 struct Point 11 { 12 double x, y; 13 Point(double xx=0, double yy=0) :x(xx),y(yy) {} 14 }; 15 typedef Point Vector; 16 17 Point read_point(void) 18 { 19 double x, y; 20 scanf("%lf%lf", &x, &y); 21 return Point(x, y); 22 } 23 24 const double EPS = 1e-7; 25 const double PI = acos(-1.0); 26 27 Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } 28 29 Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } 30 31 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } 32 33 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } 34 35 bool operator < (const Point& a, const Point& b) 36 { return a.x < b.x || (a.x == b.x && a.y < b.y); } 37 38 int dcmp(double x) 39 { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; } 40 41 bool operator == (const Point& a, const Point& b) 42 { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } 43 44 double Dot(Vector A, Vector B) 45 { return A.x*B.x + A.y*B.y; } 46 47 double Length(Vector A) { return sqrt(Dot(A, A)); } 48 49 double Angle(Vector A, Vector B) 50 { return acos(Dot(A, B) / Length(A) / Length(B)); } 51 52 double Angle2(Vector A) { return atan2(A.y, A.x); } 53 54 Vector VRotate(Vector A, double rad) 55 { 56 return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); 57 } 58 59 Vector Normal(Vector A) 60 { 61 double l = Length(A); 62 return Vector(-A.y/l, A.x/l); 63 } 64 65 double Change(double r) { return r / PI * 180.0; } 66 67 double Cross(Vector A, Vector B) 68 { return A.x*B.y - A.y*B.x; } 69 70 struct Circle 71 { 72 double x, y, r; 73 Circle(double x=0, double y=0, double r=0):x(x), y(y), r(r) {} 74 Point point(double a) 75 { 76 return Point(x+r*cos(a), y+r*sin(a)); 77 } 78 }; 79 80 const int maxn = 1010; 81 char s[maxn]; 82 83 int ID(char* s) 84 { 85 int l = strlen(s); 86 switch(l) 87 { 88 case 19: return 0; 89 case 15: return 1; 90 case 23: return 2; 91 case 46: return 3; 92 case 33: return 4; 93 case 43: return 5; 94 default: return -1; 95 } 96 } 97 98 void Solve(double A1, double B1, double C1, double A2, double B2, double C2, double& ansx, double& ansy) 99 {100 ansx = (B1*C2 - B2*C1) / (A1*B2 - A2*B1);101 ansy = (C2*A1 - C1*A2) / (B1*A2 - B2*A1); 102 }103 104 void problem0()105 {106 Point A, B, C;107 scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);108 double A1 = B.x-A.x, B1 = B.y-A.y, C1 = (A.x*A.x-B.x*B.x+A.y*A.y-B.y*B.y)/2;109 double A2 = C.x-A.x, B2 = C.y-A.y, C2 = (A.x*A.x-C.x*C.x+A.y*A.y-C.y*C.y)/2;110 Point ans;111 Solve(A1, B1, C1, A2, B2, C2, ans.x, ans.y);112 double r = Length(ans - A);113 printf("(%.6lf,%.6lf,%.6lf)\n", ans.x, ans.y, r);114 }115 116 void problem1()117 {118 Point A, B, C;119 scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);120 double a = Length(B-C), b = Length(A-C), c = Length(A-B);121 double l = a+b+c;122 Point ans = (A*a+B*b+C*c)/l;123 double r = fabs(Cross(A-B, C-B)) / l;124 printf("(%.6lf,%.6lf,%.6lf)\n", ans.x, ans.y, r);125 }126 127 void problem2()128 {129 Circle C;130 Point P, O;131 scanf("%lf%lf%lf%lf%lf", &C.x, &C.y, &C.r, &P.x, &P.y);132 double ans[2];133 O.x = C.x, O.y = C.y;134 double d = Length(P-O);135 int k = dcmp(d-C.r);136 if(k < 0)137 {138 printf("[]\n");139 return;140 }141 else if(k == 0)142 {143 ans[0] = Change(Angle2(P-O)) + 90.0;144 while(ans[0] >= 180.0) ans[0] -= 180.0;145 while(ans[0] < 0) ans[0] += 180.0;146 printf("[%.6lf]\n", ans[0]);147 return;148 }149 else150 {151 double ag = asin(C.r/d);152 double base = Angle2(P-O);153 ans[0] = base + ag, ans[1] = base - ag;154 ans[0] = Change(ans[0]), ans[1] = Change(ans[1]);155 while(ans[0] >= 180.0) ans[0] -= 180.0;156 while(ans[0] < 0) ans[0] += 180.0;157 while(ans[1] >= 180.0) ans[1] -= 180.0;158 while(ans[1] < 0) ans[1] += 180.0;159 if(ans[0] >= ans[1]) swap(ans[0], ans[1]);160 printf("[%.6lf,%.6lf]\n", ans[0], ans[1]);161 }162 }163 164 vector<Point> sol;165 struct Line166 {167 Point p;168 Vector v;169 Line() { }170 Line(Point p, Vector v): p(p), v(v) {}171 Point point(double t)172 {173 return p + v*t;174 }175 Line move(double d)176 {177 return Line(p + Normal(v)*d, v);178 }179 };180 Point GetIntersection(Line a, Line b)181 {182 Vector u = a.p - b.p;183 double t = Cross(b.v, u) / Cross(a.v, b.v);184 return a.p + a.v*t;185 }186 struct Circle2187 {188 Point c; //圆心189 double r; //�径190 Point point(double a)191 {192 return Point(c.x+r*cos(a), c.y+r*sin(a));193 }194 };195 //两圆相交并返�交点个数 196 int getLineCircleIntersection(Line L, Circle2 C, vector<Point>& sol)197 {198 double t1, t2;199 double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;200 double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;201 double delta = f*f - 4*e*g; //判别�202 if(dcmp(delta) < 0) return 0; //相离203 if(dcmp(delta) == 0) //相切204 {205 t1 = t2 = -f / (2 * e);206 sol.push_back(L.point(t1));207 return 1;208 }209 //相交210 t1 = (-f - sqrt(delta)) / (2 * e); sol.push_back(L.point(t1));211 t2 = (-f + sqrt(delta)) / (2 * e); sol.push_back(L.point(t2));212 return 2;213 }214 void problem3()215 {216 Circle2 C;217 Point A, B;218 scanf("%lf%lf%lf%lf%lf%lf%lf", &C.c.x, &C.c.y, &A.x, &A.y, &B.x, &B.y, &C.r);219 Vector v = (A-B)/Length(A-B)*C.r;220 //printf("%lf\n", Length(v));221 Point p1 = A + Point(-v.y, v.x);222 Point p2 = A + Point(v.y, -v.x);223 //printf("%lf\n%lf", Length(p1-C.c), Length(p2-C.c));224 Line L1(p1, v), L2(p2, v);225 226 sol.clear();227 int cnt = getLineCircleIntersection(L1, C, sol);228 cnt += getLineCircleIntersection(L2, C, sol);229 sort(sol.begin(), sol.end());230 if(cnt == 0) { printf("[]\n"); return; }231 printf("[");232 for(int i = 0; i < cnt-1; ++i) printf("(%.6lf,%.6lf),", sol[i].x, sol[i].y);233 printf("(%.6lf,%.6lf)]\n", sol[cnt-1].x, sol[cnt-1].y);234 }235 236 void problem4()237 {238 double r;239 Point A, B, C, D, E, ans[4];240 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);241 Line a(A, B-A), b(C, D-C);242 Line L1 = a.move(r), L2 = a.move(-r);243 Line L3 = b.move(r), L4 = b.move(-r);244 ans[0] = GetIntersection(L1, L3);245 ans[1] = GetIntersection(L1, L4);246 ans[2] = GetIntersection(L2, L3);247 ans[3] = GetIntersection(L2, L4);248 sort(ans, ans+4);249 printf("[");250 for(int i = 0; i < 3; ++i) printf("(%.6lf,%.6lf),", ans[i].x, ans[i].y);251 printf("(%.6lf,%.6lf)]\n", ans[3].x, ans[3].y);252 }253 254 int getCircleCircleIntersection(Circle2 C1, Circle2 C2, vector<Point>& sol)255 {256 double d = Length(C1.c - C2.c);257 if(dcmp(d) == 0)258 {259 if(dcmp(C1.r - C2.r) == 0) return -1;260 return 0;261 }262 if(dcmp(C1.r + C2.r - d) < 0) return 0;263 if(dcmp(fabs(C1.r - C2.r) - d) > 0) return 0;264 265 double a = Angle2(C2.c - C1.c);266 double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (2*C1.r*d));267 Point p1 = C1.point(a+da), p2 = C1.point(a-da);268 sol.push_back(p1);269 if(p1 == p2) return 1;270 sol.push_back(p2);271 return 2;272 }273 274 void problem5()275 {276 Circle2 C1, C2;277 double r;278 vector<Point> sol;279 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);280 double d = Length(C1.c - C2.c);281 C1.r += r, C2.r += r;282 if(dcmp(C1.r+C2.r-d) < 0) { printf("[]\n"); return; }283 int n = getCircleCircleIntersection(C1, C2, sol);284 sort(sol.begin(), sol.end());285 printf("[");286 for(int i = 0; i < n-1; ++i) printf("(%.6lf,%.6lf),", sol[i].x, sol[i].y);287 printf("(%.6lf,%.6lf)]\n", sol[n-1].x, sol[n-1].y);288 }289 290 int main()291 {292 #ifdef LOCAL293 freopen("12304in.txt", "r", stdin);294 #endif295 296 while(scanf("%s", s) == 1)297 {298 int proID = ID(s);299 switch(proID)300 {301 case 0: problem0(); break;302 case 1: problem1(); break;303 case 2: problem2(); break;304 case 3: problem3(); break;305 case 4: problem4(); break;306 case 5: problem5(); break;307 default: break;308 }309 }310 311 return 0;312 }
UVa 12304 (6个二维几何问题合集) 2D Geometry 110 in 1!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。