| 10 | return atan2(ad.y, sqrt(ad.x*ad.x + ad.z*ad.z)) < |
| 11 | atan2(bd.y, sqrt(bd.x*bd.x + bd.z*bd.z)); } |
| 12 | set<vi> gift_wrap(vector<point3d> points) { |
| 13 | int n = points.size(), lowi = 0, lowj = 0; |
| 14 | set<vi> res; set<ii> vis; queue<ii> q; |
| 15 | if (n < 3) return res; |
| 16 | rep(i,1,n) if (cmpy(points[i], points[lowi])) lowi = i; |
| 17 | slp = points[lowi]; |
| 18 | if (lowj == lowi) lowj++; |
| 19 | rep(j,lowj+1,n) |
| 20 | if (j!=lowi && cmpsl(points[j], points[lowj])) lowj=j; |
| 21 | q.push(ii(min(lowi,lowj), max(lowi,lowj))); |
| 22 | while (!q.empty()) { |
| 23 | ii cur = q.front(); q.pop(); |
| 24 | if (!vis.insert(cur).second) continue; |
| 25 | int mni = 0, mxi = 0; |
| 26 | while (mni==cur.first || mni==cur.second) mni++,mxi++; |
| 27 | rep(i,0,n) { |
| 28 | if (i == cur.first || i == cur.second) continue; |
| 29 | if (mixed(points[cur.second] - points[cur.first], |
| 30 | points[mni] - points[cur.first], |
| 31 | points[i] - points[cur.first]) < 0) mni = i; |
| 32 | if (mixed(points[cur.second] - points[cur.first], |
| 33 | points[mxi] - points[cur.first], |
| 34 | points[i] - points[cur.first]) > 0) mxi = i; } |
| 35 | vi a = {cur.first,cur.second}, b = {mni,mxi}; |
| 36 | rep(i,0,2) { |
| 37 | if (b[i] == -1) continue; |
| 38 | rep(j,0,2) q.push({min(b[i],a[j]), max(b[i],a[j])}); |
| 39 | vi v = {a[0], a[1], b[i]}; |
| 40 | sort(v.begin(), v.end()); |
| 41 | res.insert(v); } } return res; } |
| 42 | // vim: cc=60 ts=2 sts=2 sw=2: |