把每个交点映射为单独的id，map去重。对每个点建立相邻点的链表。枚举点，用相邻点链表找最左点，迭代绕出凸包，枚举圆判凸包与圆相交。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<vector> 6 #include<algorithm> 7 #include<iostream> 8 #include<map> 9 using namespace std; 10 const int maxn = 41; 11 const int maxm = maxn * maxn; 12 const double eps = 1e-8; 13 const double pi = acos(-1.0); 14 int dcmp(double x) 15 { 16 if(x < -eps) return -1; 17 return x > eps; 18 } 19 struct Point 20 { 21 double x, y, r; 22 bool operator <(const Point &b)const 23 { 24 if(dcmp(x - b.x) == 0) 25 return y < b.y; 26 return x < b.x; 27 } 28 }; 29 typedef struct 30 { 31 Point s, e; 32 double ang, d; 33 } Line; 34 35 inline double det(double x1, double y1, double x2, double y2) 36 { 37 return x1 * y2 - x2 * y1; 38 } 39 double cross(Point a, Point b, Point c) 40 { 41 return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); 42 } 43 Point MakePoint(double xx, double yy) 44 { 45 Point res; 46 res.x = xx, res.y = yy; 47 return res; 48 } 49 50 51 int n, m, L, W, pnum; 52 vector<Point> ap; 53 vector<int> lp[maxn], adjp[maxm]; 54 vector<Line> l; 55 vector<double> ans[maxn]; 56 map<Point, int> M; 57 Point c[maxn]; 58 bool visp[maxm]; 59 60 Line SetLine(Point a, Point b) 61 { 62 Line l; 63 l.s = a; 64 l.e = b; 65 l.ang = atan2(b.y - a.y, b.x - a.x); 66 if(dcmp(a.x - b.x)) l.d = (a.x * b.y - b.x * a.y) / fabs(a.x - b.x); 67 else l.d = (a.x * b.y - b.x * a.y) / fabs(a.y - b.y); 68 return l; 69 } 70 double dotdet(double x1, double y1, double x2, double y2) 71 { 72 return x1 * x2 + y1 * y2; 73 } 74 double dot(Point a, Point b, Point c) 75 { 76 return dotdet(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); 77 } 78 int betweenCmp(Point a, Point b, Point c) 79 { 80 return dcmp(dot(a, b, c)); 81 } 82 bool segcross(Point a, Point b, Point c, Point d, Point &p) 83 { 84 double s1, s2, s3, s4; 85 int d1, d2, d3, d4; 86 d1 = dcmp(s1 = cross(a, b, c)); 87 d2 = dcmp(s2 = cross(a, b, d)); 88 d3 = dcmp(s3 = cross(c, d, a)); 89 d4 = dcmp(s4 = cross(c, d, b)); 90 if((d1 ^ d2) == -2 && (d3 ^ d4 == -2)) 91 { 92 p.x = (c.x * s2 - d.x * s1) / (s2 - s1); 93 p.y = (c.y * s2 - d.y * s1) / (s2 - s1); 94 return true; 95 } 96 if(d1 == 0 && betweenCmp(c, a, b) <= 0) 97 { 98 p = c; 99 return true; 100 } 101 if(d2 == 0 && betweenCmp(d, a, b) <= 0) 102 { 103 p = d; 104 return true; 105 } 106 if(d3 == 0 && betweenCmp(a, c, d) <= 0) 107 { 108 p = a; 109 return true; 110 } 111 if(d4 == 0 && betweenCmp(b, c, d) <= 0) 112 { 113 p = b; 114 return true; 115 } 116 return false; 117 } 118 119 bool CrossPoint(const Line &la, const Line &lb, Point &p) 120 { 121 return segcross(la.s, la.e, lb.s, lb.e, p); 122 } 123 bool Parallel(const Line &la, const Line &lb) 124 { 125 return !dcmp( (la.e.x - la.s.x) * (lb.e.y - lb.s.y) - 126 (la.e.y - la.s.y) * (lb.e.x - lb.s.x) ); 127 } 128 double PolygonArea(vector<int> p) 129 { 130 if(p.size() < 4) return 0.0; 131 double s = ap[p[0]].y * (ap[p[p.size() - 2]].x - ap[p[1]].x); 132 for(int i = 1; i < p.size() - 1; ++ i) 133 s += ap[p[i]].y * (ap[p[i - 1]].x - ap[p[i + 1]].x); 134 return fabs(s * 0.5); 135 } 136 inline double CalLen(double a, double b) 137 { 138 return sqrt(a * a + b * b); 139 } 140 inline double CalDis(Point a, Point b) 141 { 142 return CalLen(a.x - b.x, a.y - b.y); 143 } 144 inline bool InCir(Point a, Point b) 145 { 146 return dcmp(CalDis(a, b) - b.r) < 0; 147 } 148 inline bool OnCir(Point a, Point b) 149 { 150 return dcmp(CalDis(a, b) - b.r) == 0; 151 } 152 double DisPtoL(Point p, Point a, Point b) 153 { 154 return fabs(cross(p, a, b)) / CalDis(a, b); 155 } 156 bool EqualPoint(Point a, Point b) 157 { 158 return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; 159 } 160 bool SegIntersCircle(Point a, Point b, Point c) 161 { 162 Point t = c; 163 t.x += a.y - b.y; 164 t.y += b.x - a.x; 165 return cross(a, c, t) * cross(b, c, t) < eps && 166 DisPtoL(c, a, b) - c.r < -eps; 167 } 168 bool JudgePiece(int i, vector<int> ps) 169 { 170 int j, k, cnt = 0; 171 for(j = 1; j < ps.size(); ++ j) 172 { 173 if(InCir(ap[ps[j]], c[i])) return true; 174 else if(OnCir(ap[ps[j]], c[i])) ++ cnt; 175 } 176 if(cnt >= 2) return true; 177 for(j = 1; j < ps.size(); ++ j) 178 for(k = j + 1; k < ps.size(); ++ k) 179 { 180 if(SegIntersCircle(ap[ps[j]], ap[ps[k]], c[i])) 181 return true; 182 } 183 for(j = 1; j < ps.size(); ++ j) 184 if(cross(ap[ps[j - 1]], ap[ps[j]], c[i]) < -eps) return false; 185 return true; 186 } 187 void FindPiece(int s0, int s1) 188 { 189 vector<int> ps; 190 int i, j, nex = s1, ori = s0; 191 double s; 192 ps.push_back(s0); 193 ps.push_back(s1); 194 while(nex != ori) 195 { 196 nex = -1; 197 for(i = 0; i < adjp[s1].size(); ++ i) 198 { 199 if(EqualPoint(ap[adjp[s1][i]], ap[s0])) continue; 200 if(cross(ap[s0], ap[s1], ap[adjp[s1][i]]) > -eps && 201 (nex == -1 || cross(ap[s1], ap[nex], ap[adjp[s1][i]]) > eps)) 202 nex = adjp[s1][i]; 203 } 204 if(nex != -1 && (!visp[nex] || nex == ori)) 205 ps.push_back(nex); 206 else return; 207 s0 = s1, s1 = nex; 208 } 209 s = PolygonArea(ps); 210 if(!dcmp(s)) return; 211 for(i = 0; i < m; ++ i) 212 if(JudgePiece(i, ps)) 213 ans[i].push_back(s); 214 } 215 216 bool cmp(const int &a, const int &b) 217 { 218 if(dcmp(ap[a].x - ap[b].x) == 0) 219 return ap[a].y < ap[b].y; 220 return ap[a].x < ap[b].x; 221 } 222 int main() 223 { 224 int i, j, pnum; 225 double sx, sy, ex, ey; 226 while(scanf("%d%d%d%d", &n, &m , &L, &W), n | m | L | W) 227 { 228 l.clear(); 229 n += 4; 230 M.clear(); 231 ap.clear(); 232 memset(visp, 0, sizeof(visp)); 233 l.push_back(SetLine(MakePoint(0, 0), MakePoint(L, 0))); 234 l.push_back(SetLine(MakePoint(L, 0), MakePoint(L, W))); 235 l.push_back(SetLine(MakePoint(L, W), MakePoint(0, W))); 236 l.push_back(SetLine(MakePoint(0, W), MakePoint(0, 0))); 237 for(i = 4; i < n; ++ i) 238 { 239 scanf("%lf%lf%lf%lf", &sx, &sy, &ex, &ey); 240 l.push_back(SetLine(MakePoint(sx, sy), MakePoint(ex, ey))); 241 } 242 for(i = 0; i < m; ++ i) 243 scanf("%lf%lf%lf", &c[i].x, &c[i].y, &c[i].r), ans[i].clear(); 244 for(i = 0; i < n; ++ i) lp[i].clear(); 245 for(i = pnum = 0; i < n; ++ i) 246 for(j = i + 1; j < n; ++ j) 247 { 248 Point tmp; 249 if(CrossPoint(l[i], l[j], tmp)) 250 { 251 if(!M.count(tmp)) 252 adjp[pnum].clear(), M[tmp] = pnum ++, ap.push_back(tmp); 253 lp[i].push_back(M[tmp]); 254 lp[j].push_back(M[tmp]); 255 } 256 } 257 for(i = 0; i < n; ++ i) 258 { 259 sort(lp[i].begin(), lp[i].end(), cmp); 260 for(j = 1; j < lp[i].size(); ++ j) 261 { 262 if(!EqualPoint(ap[lp[i][j]], ap[lp[i][j - 1]])) 263 { 264 adjp[lp[i][j]].push_back(lp[i][j - 1]); 265 adjp[lp[i][j - 1]].push_back(lp[i][j]); 266 } 267 } 268 } 269 for(i = 0; i < pnum; ++ i) 270 { 271 if(!visp[i]) 272 { 273 visp[i] = true; 274 for(j = 0; j < adjp[i].size(); ++ j) 275 if(!visp[adjp[i][j]])FindPiece(i, adjp[i][j]); 276 } 277 } 278 for(i = 0; i < m; ++ i) 279 { 280 sort(ans[i].begin(), ans[i].end()); 281 printf("%d", ans[i].size()); 282 for(j = 0; j < ans[i].size(); ++ j) 283 printf(" %.2f", ans[i][j]); 284 printf("\n"); 285 } 286 printf("\n"); 287 } 288 return 0; 289 }