Advertisement
Guest User

Untitled

a guest
Aug 1st, 2017
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <set>
  4. #include <map>
  5. #include <utility>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <string>
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. #define mp make_pair
  13. #define pb push_back
  14. #define sz(a) int((a).size())
  15. #define forn(i, n) for (int i=0; i<(n); ++i)
  16.  
  17. typedef pair<int,int> pii;
  18. typedef long long ll;
  19. typedef long double ld;
  20.  
  21. const ld eps = 0.01;
  22. const int maxn = 128;
  23.  
  24. struct point
  25. {
  26.   ld x, y;
  27. };
  28.  
  29. ld dot(const point& a, const point& b, const point& c)
  30. {
  31.   return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y);
  32. }
  33. ld cross(const point& a, const point& b, const point& c)
  34. {
  35.   return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
  36. }
  37.  
  38. ld dist(const point& a, const point& b)
  39. {
  40.   return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
  41. }
  42.  
  43. ld ang(const point& a, const point& b, const point& c)
  44. {
  45.   ld d = dot(a, b, c);
  46.   d /= dist(a, b);
  47.   d /= dist(a, c);
  48.   return acos(d);
  49. }
  50.  
  51. void norm(point a[3])
  52. {
  53. //  printf("cross = %.4f\n", (double)cross(a[0], a[1], a[2]));
  54. //  if (cross(a[0], a[1], a[2]) > 0)    swap(a[1], a[2]);
  55. //  printf("cross2 = %.4f\n", (double)cross(a[0], a[1], a[2]));
  56. }
  57.  
  58.  
  59. point a[maxn][3];
  60. point b[maxn][3];
  61. point aa[3], bb[3], cc[3];
  62. int p[3], q[3], w[3];
  63. int u[maxn];
  64. int n;
  65.  
  66. inline bool solve2(point a[3], point b[3], point c[3])
  67. {
  68.   if (fabs(dist(a[0], a[2]) - dist(b[0], b[2])) > eps) return false;
  69.   if (fabs(ang(a[0], a[1], a[2]) - ang(b[0], b[1], b[2])) > eps) return false;
  70.   if (fabs(dist(a[2], a[1]) - dist(c[0], c[2])) > eps) return false;
  71.   if (fabs(dist(b[1], b[2]) - dist(c[0], c[1])) > eps) return false;
  72.   if (fabs(ang(a[1], a[2], a[0]) - ang(c[2], c[0], c[1])) > eps) return false;
  73.   if (fabs(dist(a[0], a[1]) - dist(b[0], b[1]) - dist(c[1], c[2])) > eps) return false;
  74.   return true;
  75. }
  76.  
  77.  
  78. inline bool solve(point a[3], point b[3], point c[3])
  79. {
  80.   forn (i, 3) w[i] = i;
  81.   forn (iii, 3)
  82.   {
  83.     forn (i, 3) aa[w[i]] = a[i];
  84.     if (solve2(aa, b, c)) return true;
  85.     next_permutation(w, w+3);
  86.     next_permutation(w, w+3);
  87.   }  
  88.   return false;
  89. }
  90.  
  91.  
  92. int main()
  93. {
  94.   for (int tc=1; ; ++tc)
  95.   {
  96.     scanf("%d", &n);
  97.     if (n == 0) break;
  98.     forn (i, n)
  99.     {
  100.       forn (j, 3) cin >> a[i][j].x >> a[i][j].y;
  101.       norm(a[i]);      
  102.     }
  103.  
  104.     forn (i, 2*n)
  105.     {
  106.       forn (j, 3) cin >> b[i][j].x >> b[i][j].y;
  107.       norm(b[i]);
  108.     }
  109.     forn (i, 2*n) u[i] = 0;
  110.  
  111.     printf("Case %d:\n", tc);
  112.     forn (i, n)
  113.     {
  114.       forn (j, 2*n) if (!u[j]) forn (k, 2*n) if (k!=j && !u[k])
  115.       {
  116.         forn (t, 3) p[t] = t;
  117.        
  118.         forn (iii, 3)
  119.         {
  120.           forn (t, 3) q[t] = t;
  121.           forn (t, 3) bb[t] = b[j][p[t]];
  122.  
  123.  
  124.           forn (jjj, 3)
  125.           {
  126.             forn (t, 3)  cc[t] = b[k][q[t]];
  127.             if (solve(a[i], bb, cc))
  128.             {
  129.               int x = j, y = k;
  130.               u[j] = u[k] = 1;
  131.               if (x > y) swap(x, y);
  132.               printf("Hole %d: %d, %d\n", i+1, x+1, y+1);
  133.               goto end;
  134.             }
  135.            
  136.             next_permutation(q, q+3);          
  137.             next_permutation(q, q+3);            
  138.           }                          
  139.  
  140.           next_permutation(p, p+3);          
  141.           next_permutation(p, p+3);
  142.         }
  143.        
  144.       }
  145.       end:;
  146.     }
  147.     puts("");
  148.  
  149.  
  150.   }
  151.   return 0;
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement