Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. /* Weryfikacja zadania Żołędzie
  2.  * Rozwiązanie brutalne O(n^2 log n)
  3.  *
  4.  * Autor: Michał Zawalski
  5.  */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define x first
  11. #define y second
  12.  
  13. typedef long long int lli;
  14. typedef pair<lli, lli> pkt;
  15.  
  16. pkt mn(const pkt &a, const pkt &b) {
  17.     return {a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x};
  18. }
  19.  
  20. lli mod(const pkt &a) {
  21.     return a.x*a.x+a.y*a.y;
  22. }
  23.  
  24. vector<pkt> in1, in2;
  25.  
  26. bool spr(const pkt &a, const pkt &b) {
  27.     if (mod(a) != mod(b))
  28.         return 0;
  29.    
  30. //  printf("(%lld %lld), (%lld %lld)\n", a.x, a.y, b.x, b.y);
  31.    
  32.     vector<pkt> v1, v2;
  33.    
  34.     for (auto p : in1)
  35.         v1.push_back(mn(p, b));
  36.     for (auto p : in2)
  37.         v2.push_back(mn(p, a));
  38.    
  39.     sort(v1.begin(), v1.end());
  40.     sort(v2.begin(), v2.end());
  41.    
  42.     for (int i=0; i<(int)v1.size(); i++) {
  43. //      printf(" (%lld %lld)-(%lld %lld) ", v1[i].x, v1[i].y, v2[i].x, v2[i].y);
  44.         if (v1[i] != v2[i])
  45.             return 0;
  46.     }
  47.    
  48.     return 1;
  49. }
  50.  
  51. int main() {
  52.     int n, k1 = 0, k2 = 0;
  53.     lli x, y;
  54.     scanf("%d", &n);
  55.    
  56.     for (int i=0; i<n; i++) {
  57.         scanf("%lld%lld", &x, &y);
  58.         if (x == 0 && y==0)
  59.             k1++;
  60.         else
  61.             in1.push_back({x, y});
  62.     }
  63.    
  64.    
  65.    
  66.     for (int i=0; i<n; i++) {
  67.         scanf("%lld%lld", &x, &y);
  68.         if (x == 0 && y==0)
  69.             k2++;
  70.         else
  71.             in2.push_back({x, y});
  72.     }
  73.    
  74.     if (k1 != k2) {
  75.         printf("NIE\n");
  76.         return 0;
  77.     }
  78.    
  79.     n -= k1;
  80.     if (n == 0) {
  81.         printf("TAK\n");
  82.         return 0;
  83.     }
  84.    
  85.     for (int i=0; i<1; i++) {
  86.         for (int j=0; j<n; j++) {
  87.             if (spr(in1[i], in2[j])) {
  88.                 printf("TAK\n");
  89.                 return 0;
  90.             }
  91.         }
  92.     }
  93.    
  94.     printf("NIE\n");
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement