题目是上一个随笔的题目，这次只判断交点个数不求出具体坐标，还是72.5分，看来卡O(n^2)复杂度卡得死死的。
这次的代码给出了简单的线段、射线、直线、圆两两相交的判断交点个数方法，代码放最后，下面介绍思路。
直线（射线、线段）与直线（射线、线段）相交判断
设线1的向量方程为 p = p1 + t1 * d1，线2的向量方程为 p = p2 + t2 * d2，其中d1和d2均为单位向量，若线1或线2为线段，记其长度为l1和l2。
首先先判断d1*d2 != ±1，否则两线平行无交点。
然后联立方程得 p1 + t1 * d1 = p2 + t2 * d2，即 [d1, -d2] * [t1 t2]T = p2 - p1，利用克拉默法则暴力解出t1和t2，接下来根据下表判断，若表格条件为真，则有交点。
| 线1\线2 | 线段 | 射线 | 直线 |
| 线段 | C1(t1)&&C1(t2) | C1(t1)&&C2(t2) | C1(t1) |
| 射线 | C2(t1)&&C1(t2) | C2(t1)&&C2(t2) | C2(t1) |
| 直线 | C1(t2) | C2(t2) | True |
其中 C1(t) = (t >= 0) && (t <= l)，l为线段长度，C2(t) = (t>=0)。
直线（射线、线段）与圆相交判断
设线的向量方程为p = o + t * d，d是单位向量，o是线的端点。圆的圆心为c，半径为r。
首先求出c到线的距离D和c在线上的投影点c'对应的向量方程参数t'。
o2c = c - o
t' = o2c * d
D = len(o2c - t' * d)
直线的情况
交于两点: D < r
交于一点： D == r
无交点： D > r
射线的情况
令in, at, out分别表示射线的起点o在圆内、圆上、圆外
若 D > r，无交点。
若 D == r 且 t' >= 0 ，一个交点。
若D < r ：
若in为true，一个交点。
若at为true，两个交点。
若out为true，
若t >= 0，两个交点；
若t < 0 ，无交点。
线段的情况
令in1, at1, out1分别表示线段的起点o在圆内、圆上、圆外
令in2, at2, out2分别表示线段的终点o'在圆内、圆上、圆外
若D > r，无交点。
若D == r 且 0 <= t' <= l（l是线段的长度），一个交点。
若D < r :
若 in1 && in2为true，两个端点都在圆内，无交点。
若at1 || at2为true，交点个数为at1 + at2。
若(in1 && out2) || (out1 && in2)为true，一个交点。
若out1 && out2为true：
若0 <= t' <= l，两个交点；
若 t' < 0 || t' > l，无交点。
圆与圆相交判断
圆半径r1和r2，圆心距d
交于两点: |r1 - r2| < d < r1 + r2
交于一点： d == |r1 - r2| 或 d == r1 + r2
无交点: d < |r1 - r2| 或 d > r1 + r2
代码
1 #include<iostream>
2 #include<vector>
3 #include<algorithm>
4 #include<queue>
5 #include<set>
6 #include<cmath>
7 using namespace std;
8
9 #define EPS 1e-8
10
11 #define DEBUG
12
13 int TOTAL;
14
15 enum CURVETYPE{
16 CNONE, SEGMENT, RAY, LINE, CIRCLE
17 };
18
19 enum POINTTYPE{
20 PNONE, LEFT, RIGHT, ENDPOINT, DIR, CENTER, INTX
21 };
22
23 struct Point2{
24 double x;
25 double y;
26
27 // 点所在的曲线编号
28 long long int n;
29 POINTTYPE ptype;
30 // 交点所在的曲线编号
31 long long int n1;
32 long long int n2;
33
34 Point2(double xx, double yy, long long int nn, POINTTYPE e) : x(xx), y(yy), n(nn), ptype(e){
35 n1 = 0;
36 n2 = 0;
37 }
38
39 Point2() : x(0),y(0),n(0),ptype(POINTTYPE::PNONE),n1(0),n2(0){}
40
41 bool operator== (const Point2& p) const{
42 return abs(x - p.x) < EPS && abs(y - p.y) < EPS && ptype == p.ptype && n == p.n && n1 == p.n1 && n2 == p.n2;
43 }
44
45 //需要最大堆，对小于号重载
46
47 bool operator < (const Point2& p) const{
48 return (x < p.x) || (abs(x - p.x) < EPS &&
49 (y < p.y || (abs(y - p.y) < EPS &&
50 (ptype < p.ptype || (ptype == p.ptype &&
51 (n < p.n || (n == p.n &&
52 n1 < p.n1 || (n1 == p.n1 &&
53 n2 < p.n2))))))));
54 }
55
56 Point2 operator- (const Point2& p) const{
57 auto res = Point2();
58 res.x = x - p.x;
59 res.y = y - p.y;
60 return res;
61 }
62
63 Point2 operator+ (const Point2& p) const{
64 auto res = Point2();
65 res.x = x + p.x;
66 res.y = y + p.y;
67 return res;
68 }
69
70 double operator* (const Point2& p) const{
71 return x * p.x + y * p.y;
72 }
73
74 Point2 operator* (const double k) const{
75 auto res = *this;
76 res.x *= k;
77 res.y *= k;
78 return res;
79 }
80
81 double norm(){
82 return sqrt(x * x + y * y);
83 }
84
85 // 需要最小堆，对大于号重载
86 friend bool operator > (const Point2& p1, const Point2& p2) {
87 return (p1.x > p2.x) || (abs(p1.x - p2.x) < EPS &&
88 (p1.y > p2.y || (abs(p1.y - p2.y) < EPS &&
89 (p1.ptype > p2.ptype || (p1.ptype == p2.ptype &&
90 (p1.n > p2.n || (p1.n == p2.n &&
91 (p1.n1 > p2.n1 || (p1.n1 == p2.n1 &&
92 p1.n2 >p2.n2)))))))));
93 }
94
95 friend ostream& operator<<(ostream& out, const Point2& p){
96 string str[] = {"PNONE", "LEFT", "RIGHT", "ENDPOINT", "DIR", "CENTER", "INTX"};
97 if(p.ptype != INTX)
98 out << "( " << p.x << " , " << p.y << " ) " << p.n << " " << str[p.ptype] << endl;
99 else
100 out << "( " << p.x << " , " << p.y << " ) " << p.n1 << " " << p.n2 << " " << str[p.ptype] << endl;
101 return out;
102 }
103 };
104
105 vector<Point2> vecPoints;
106 class Curve{
107 public:
108 // 曲线编号
109 int n;
110 CURVETYPE ctype;
111
112 Curve(){
113 n = 0;
114 ctype = CURVETYPE::CNONE;
115 }
116
117 Curve(int nn, CURVETYPE ct) : n(nn), ctype(ct){}
118
119 //虚函数得实现，不然没有vtable
120 virtual void intersection(Curve*& c, set<Point2>& intxPoints){
121 cout << "Curve intersection" << endl;
122 };
123
124 bool getLineIntxLinePoint(Point2& p1, Point2& dir1, Point2& p2, Point2& dir2, double& t0, double& t1){
125 if(abs(abs(dir1 * dir2) - 1) < EPS)
126 return false;
127
128 // 解射线方程，然后判断是否在线段内
129 auto denom = -dir1.x * dir2.y + dir2.x * dir1.y;
130 auto p = p2 - p1;
131 t0 = (-p.x * dir2.y + p.y * dir2.x) / denom;
132 t1 = (p.y * dir1.x - p.x * dir1.y) / denom;
133
134 return true;
135 };
136
137 bool getLineIntxCirclePoint(Point2& p, Point2& dir, Point2& center, double r, double& t0, double& t1){
138 auto p2c = center - p;
139 auto p2cDdir = p2c * dir;
140 auto d = (p2c - dir * p2cDdir).norm();
141 if(d > r)
142 return false;
143
144 t0 = (p2cDdir + sqrt(p2cDdir * p2cDdir - (p2c * p2c - r * r)));
145 t1 = (p2cDdir - sqrt(p2cDdir * p2cDdir - (p2c * p2c - r * r)));
146
147 return true;
148 }
149
150 Point2 getLineIntxPoint(Point2& p, Point2& dir, double t, int n1, int n2){
151 auto res = Point2();
152 res.x = p.x + t * dir.x;
153 res.y = p.y + t * dir.y;
154 res.ptype = INTX;
155 res.n1 = n1;
156 res.n2 = n2;
157 vecPoints.push_back(res);
158 return move(res);
159 }
160
161 friend ostream& operator<<(ostream& out, Curve& c);
162
163 };
164
165 class Line : public Curve{
166 public:
167 Point2 p1;
168 Point2 p2;
169 Point2 dir;
170 // p1 p2的长度
171 double t;
172
173 Line() : Curve(0, CURVETYPE::CNONE){
174 p1 = Point2();
175 p2 = Point2();
176 dir = Point2();
177 t = 0;
178 }
179
180 Line(int a, int b, int c, int d, int nn, CURVETYPE type) : Curve(nn, type) {
181 p1 = Point2(a, b, nn, LEFT);
182 p2 = Point2(c, d, nn, RIGHT);
183 t = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
184 dir = Point2((p2.x - p1.x) / t, (p2.y - p1.y) / t, nn, DIR);
185 }
186
187 void lineIntxLine(Curve* c);
188
189 void lineIntxCircle(Curve *c);
190
191 void intersection(Curve* c){
192 switch (c->ctype)
193 {
194 //变量的定义不能放在goto之后
195 case SEGMENT :
196 case RAY :
197 case LINE :
198 lineIntxLine(c);
199 break;
200 case CIRCLE :
201 lineIntxCircle(c);
202 break;
203 default:
204 break;
205 }
206 }
207 };
208
209 class Circle : public Curve{
210 public:
211 Point2 center;
212 double R;
213
214 Circle() : Curve(0, CURVETYPE::CIRCLE){
215 center = Point2();
216 R = 0;
217 }
218
219 Circle(int a, int b, double r, int nn) : Curve(nn, CURVETYPE::CIRCLE){
220 center = Point2(a, b, nn, CENTER);
221 R = r;
222 }
223
224 void circleIntxCircle(Curve* c);
225
226 void judgePointCircle(Point2& p, bool& in, bool& at, bool& out){
227 auto d = (p - center).norm();
228 in = d < R;
229 at = abs(d - R) < EPS;
230 out = d > R;
231 }
232
233 double lineCircleDistance(Point2& p, Point2& dir, double& t){
234 auto p2c = center - p;
235 t = p2c * dir;
236 return (p2c - dir * t).norm();
237 }
238
239 void intersection(Curve* c){
240 switch (c->ctype)
241 {
242 case LINE :
243 dynamic_cast<Line*> (c)->intersection(dynamic_cast<Curve*>(this));
244 break;
245 case CIRCLE :
246 circleIntxCircle(c);
247 break;
248 default:
249 break;
250 }
251 }
252 };
253
254 void Line::lineIntxLine(Curve* c){
255 auto line = dynamic_cast<Line*>(c);
256 double t0, t1;
257 // 按照直线相交计算得出参数，再进一步判断吧
258 if(!getLineIntxLinePoint(p1, dir, line->p1, line->dir, t0, t1))
259 return;
260
261 if(ctype == SEGMENT){
262 if(t0 < 0 || t0 > t) return;
263 if((line->ctype == SEGMENT) && (t1 < 0 || t1 > line->t)) return;
264 if((line->ctype == RAY) && (t1 < 0)) return;
265 }else if(ctype == RAY){
266 if(t0 < 0) return;
267 if((line->ctype == SEGMENT) && (t1 < 0 || t1 > line->t)) return;
268 if((line->ctype == RAY) && (t1 < 0)) return;
269 }else if(ctype == LINE){
270 if((line->ctype == SEGMENT) && (t1 < 0 || t1 > line->t)) return;
271 if((line->ctype == RAY) && (t1 < 0)) return;
272 }
273 TOTAL++;
274 return;
275 }
276
277 void Line::lineIntxCircle(Curve* c){
278 auto circle = dynamic_cast<Circle*>(c);
279 double t; // 投影点的参数t
280 auto d = circle->lineCircleDistance(p1, dir, t);
281 if(d > circle->R)
282 return;
283
284 // 切点的情况
285 if(abs(d - circle->R) < EPS){
286 if(ctype == LINE){
287 TOTAL++;
288 }else if(ctype == RAY){
289 if(t > 0 || abs(t - 0) < EPS)
290 TOTAL++;
291 }else if(ctype == SEGMENT){
292 if((t > 0 || abs(t - 0) < EPS) && (t < this->t || abs(t - this->t) < EPS))
293 TOTAL++;
294 }
295 return;
296 }
297
298 //
299 if(ctype == LINE)
300 TOTAL+=2;
301 else if(ctype == SEGMENT){
302 bool in1, in2, at1, at2, out1, out2;
303 circle->judgePointCircle(p1, in1, at1, out1);
304 circle->judgePointCircle(p2, in2, at2, out2);
305 // 都在圆里
306 if(in1 && in2) return;
307 // 在圆上
308 if(at1 || at2){TOTAL+= at1 + at2; return;}
309 // 一内一外
310 if((in1 && out2) || (out1 && in2)){TOTAL++; return;}
311 // 两个在外，且由上面的判断，圆心到线的距离已经小于 r
312 if(out1 && out2){
313 // 如果圆心的投影在线段上，则必有两个交点
314 if((t > 0 || abs(t - 0) < EPS) && (t < this->t || abs(t - this->t) < EPS))
315 TOTAL+= 2;
316 // 否则没有交点
317 return;
318 }
319 }else if(ctype == RAY){
320 bool in, at, out;
321 circle->judgePointCircle(p1, in, at, out);
322
323 // 端点在圆内只有一个交点
324 if(in) {TOTAL++; return;}
325
326 // 端点在圆上，且圆心到线的距离小于 r， 看圆心在射线的投影在前在后
327 if(at){
328 if(t < 0) TOTAL++;
329 if(t > 0) TOTAL+=2;
330 return;
331 }
332
333 // 端点在圆外，且由上面的判断，圆心到线的距离已经小于 r，此时判断p2c和dir的夹角即可，也就是t
334 if(out) {
335 if(t > 0) TOTAL+=2;
336 return;
337 }
338 }
339
340 }
341
342 void Circle::circleIntxCircle(Curve* c){
343 auto cc = dynamic_cast<Circle*>(c);
344 auto d = (center - cc->center).norm();
345 if(d > R + cc->R || d < abs(R - cc->R))
346 return;
347 if(abs(d - R - cc->R) < EPS || abs(d - abs(R - cc->R)) < EPS)
348 TOTAL++;
349 else
350 TOTAL+=2;
351 }
352
353 // 如果要在Curve类内定义，只能是Segment*，因为前向声明不能使用对象，只能使用指针
354 ostream& operator<<(ostream& out, Curve& c) {
355 string str[] = {"CNONE", "SEGMENT", "RAY", "LINE", "CIRCLE"};
356 if(c.ctype == CNONE)
357 out << c.n << " " << str[c.ctype] << endl;
358 else if(c.ctype == SEGMENT) {
359 // dynamic_cast必须有虚函数
360 Line& s = dynamic_cast<Line&>(c);
361 out << s.n << " " << str[s.ctype] << " (" << s.p1.x << " , " << s.p1.y << ") (" << s.p2.x << " , " << s.p2.y << ") "
362 << s.t << " (" << s.dir.x << " , " << s.dir.y << ")" << endl;
363 }else if(c.ctype == RAY){
364 Line& r = dynamic_cast<Line&>(c);
365 out << r.n << " " << str[r.ctype] << " (" << r.p1.x << " , " << r.p1.y << ") " << " (" << r.dir.x << " , " << r.dir.y << ")" << endl;
366 }else if(c.ctype == LINE){
367 Line& l = dynamic_cast<Line&>(c);
368 out << l.n << " " << str[l.ctype] << " (" << l.p1.x << " , " << l.p1.y << ") (" << l.dir.x << " , " << l.dir.y << ") " << endl;
369 }else if(c.ctype == CIRCLE){
370 Circle& cc = dynamic_cast<Circle&>(c);
371 out << cc.n << " " << str[cc.ctype] << " (" << cc.center.x << " , " << cc.center.y << ") " << cc.R << endl;
372 }
373
374 return out;
375 }
376
377
378 int N, S, R, L, C;
379 // 多态只能用指针，不能用对象，不然会隐式转换对象的内容而产生丢失
380 vector<Curve*> curves;
381
382 int main(){
383 curves.push_back(new Curve());
384 cin >> S >> R >> L >> C;
385 int a,b,c,d;
386 for(int i = 1; i <= S + R + L; i ++){
387 cin >> a >> b >> c >> d;
388 CURVETYPE t = CNONE;
389 if(i <= S)
390 t = SEGMENT;
391 else if(i <= S + R)
392 t = RAY;
393 else if(i <= S + R + L)
394 t = LINE;
395 if(a < c)
396 curves.push_back(new Line(a, b, c, d, i, t));
397 else
398 curves.push_back(new Line(a, b, c, d, i, t));
399 }
400 for(int i = S + R + L + 1; i <= S + R + L + C; i ++){
401 cin >> a >> b >> c;
402 curves.push_back(new Circle(a, b, c, i));
403 }
404
405 #ifndef DEBUG
406 for(auto c :curves)
407 cout << *c;
408 #endif
409
410 for(int i = 1; i <= S + R + L + C; i ++) {
411 if(i <= S + R + L) {
412 auto s = dynamic_cast<Line*> (curves[i]);
413 for(int j = i + 1; j <= S + L + R + C; j ++){
414 s->intersection(curves[j]);
415 }
416 }else if(i <= S + R + L + C) {
417 auto s = dynamic_cast<Circle*> (curves[i]);
418 for(int j = i + 1; j <= S + L + R + C; j ++){
419 s->intersection(curves[j]);
420 }
421 }
422 }
423
424 cout << TOTAL;
425
426 return 0;
427 }
标签：PA1,p1,return,res,t1,Point2,&&,CG2017,Crossroad From： https://www.cnblogs.com/HXLGY/p/16839946.html