Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
- #include <utility>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <iostream>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define sz(a) int((a).size())
- #define forn(i, n) for (int i=0; i<(n); ++i)
- typedef pair<int,int> pii;
- typedef long long ll;
- typedef long double ld;
- const ld eps = 0.01;
- const int maxn = 128;
- struct point
- {
- ld x, y;
- };
- ld dot(const point& a, const point& b, const point& c)
- {
- return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y);
- }
- ld cross(const point& a, const point& b, const point& c)
- {
- return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
- }
- ld dist(const point& a, const point& b)
- {
- return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
- }
- ld ang(const point& a, const point& b, const point& c)
- {
- ld d = dot(a, b, c);
- d /= dist(a, b);
- d /= dist(a, c);
- return acos(d);
- }
- void norm(point a[3])
- {
- // printf("cross = %.4f\n", (double)cross(a[0], a[1], a[2]));
- // if (cross(a[0], a[1], a[2]) > 0) swap(a[1], a[2]);
- // printf("cross2 = %.4f\n", (double)cross(a[0], a[1], a[2]));
- }
- point a[maxn][3];
- point b[maxn][3];
- point aa[3], bb[3], cc[3];
- int p[3], q[3], w[3];
- int u[maxn];
- int n;
- inline bool solve2(point a[3], point b[3], point c[3])
- {
- if (fabs(dist(a[0], a[2]) - dist(b[0], b[2])) > eps) return false;
- if (fabs(ang(a[0], a[1], a[2]) - ang(b[0], b[1], b[2])) > eps) return false;
- if (fabs(dist(a[2], a[1]) - dist(c[0], c[2])) > eps) return false;
- if (fabs(dist(b[1], b[2]) - dist(c[0], c[1])) > eps) return false;
- if (fabs(ang(a[1], a[2], a[0]) - ang(c[2], c[0], c[1])) > eps) return false;
- if (fabs(dist(a[0], a[1]) - dist(b[0], b[1]) - dist(c[1], c[2])) > eps) return false;
- return true;
- }
- inline bool solve(point a[3], point b[3], point c[3])
- {
- forn (i, 3) w[i] = i;
- forn (iii, 3)
- {
- forn (i, 3) aa[w[i]] = a[i];
- if (solve2(aa, b, c)) return true;
- next_permutation(w, w+3);
- next_permutation(w, w+3);
- }
- return false;
- }
- int main()
- {
- for (int tc=1; ; ++tc)
- {
- scanf("%d", &n);
- if (n == 0) break;
- forn (i, n)
- {
- forn (j, 3) cin >> a[i][j].x >> a[i][j].y;
- norm(a[i]);
- }
- forn (i, 2*n)
- {
- forn (j, 3) cin >> b[i][j].x >> b[i][j].y;
- norm(b[i]);
- }
- forn (i, 2*n) u[i] = 0;
- printf("Case %d:\n", tc);
- forn (i, n)
- {
- forn (j, 2*n) if (!u[j]) forn (k, 2*n) if (k!=j && !u[k])
- {
- forn (t, 3) p[t] = t;
- forn (iii, 3)
- {
- forn (t, 3) q[t] = t;
- forn (t, 3) bb[t] = b[j][p[t]];
- forn (jjj, 3)
- {
- forn (t, 3) cc[t] = b[k][q[t]];
- if (solve(a[i], bb, cc))
- {
- int x = j, y = k;
- u[j] = u[k] = 1;
- if (x > y) swap(x, y);
- printf("Hole %d: %d, %d\n", i+1, x+1, y+1);
- goto end;
- }
- next_permutation(q, q+3);
- next_permutation(q, q+3);
- }
- next_permutation(p, p+3);
- next_permutation(p, p+3);
- }
- }
- end:;
- }
- puts("");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement