Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7. int n;
  8. vector<int> v[21];
  9. vector<int> triangle[301];
  10. void calculatePascalsTriangle(){
  11.     int nxt = 1;
  12.     int tmp = 1;
  13.     for(int i = 0; i <= 260; i ++){
  14.         for(int j = 0; j < tmp; j ++){
  15.             triangle[i].push_back(nxt);
  16.             nxt ++;
  17.         }
  18.         tmp ++;
  19.     }
  20. }
  21. pair<int, int> findCords(int pos){
  22.     int levo = 0;
  23.     int desno = 260;
  24.     int mid, mid2;
  25.     bool da = false;
  26.     int levo2, desno2;
  27.     while(levo <= desno){
  28.         mid = (levo + desno) / 2;
  29.         levo2 = 0;
  30.         desno2 = (int)triangle[mid].size();
  31.         while(levo2 <= desno2){
  32.             mid2 = (levo2 + desno2) / 2;
  33.             if(triangle[mid][mid2] == pos){
  34.                 return make_pair(mid, mid2);
  35.             }
  36.             if(triangle[mid][mid2] < pos){
  37.                 levo2 = mid2 + 1;
  38.             }
  39.             if(triangle[mid][mid2] > pos){
  40.                 desno2 = mid2 - 1;
  41.             }
  42.         }
  43.         if(pos > triangle[mid][(int)triangle[mid].size() - 1]){
  44.             levo = mid + 1;
  45.         }
  46.         else{
  47.             desno = mid - 1;
  48.         }
  49.     }
  50.     return make_pair(-1, -1);
  51. }
  52. bool checkIfCordsAreOnTheSameLine(int x, int y){
  53.     pair<int, int> p1 = findCords(x);
  54.     pair<int, int> p2 = findCords(y);
  55.     if(p1.first == p2.first)return true;
  56.     if(p1.first != p2.first && p1.second == p2.second)return true;
  57.     if((p1.first - p2.first) == (p1.second - p2.second))return true;
  58.     return false;
  59. }
  60. int distance(int x, int y){
  61.     pair<int, int> p1 = findCords(x);
  62.     pair<int, int> p2 = findCords(y);
  63.     return max(abs(p1.first - p2.first), abs(p1.second - p2.second));
  64. }
  65. int main(int argc, const char * argv[]) {
  66.     ios_base::sync_with_stdio(false);
  67.     cin >> n;
  68.     int pos;
  69.     int sz;
  70.     for(int i = 0; i < n; i ++){
  71.         cin >> sz;
  72.         for(int j = 0; j < sz; j ++){
  73.             cin >> pos;
  74.             v[i].push_back(pos);
  75.         }
  76.     }
  77.     calculatePascalsTriangle();
  78.     int a, b, c, d, e, f;
  79.     bool da;
  80.     for(int i = 0; i < n; i ++){
  81.         sz = (int)v[i].size();
  82.         if(sz != 3 && sz != 4 && sz != 6){
  83.             cout << "NISTO\n";
  84.         }
  85.         if(sz == 3){
  86.             if(!checkIfCordsAreOnTheSameLine(v[i][0], v[i][1]) || !checkIfCordsAreOnTheSameLine(v[i][1], v[i][2]) || !checkIfCordsAreOnTheSameLine(v[i][0], v[i][2])){
  87.                 cout << "NISTO\n";
  88.             }
  89.             else{
  90.                 if(distance(v[i][0], v[i][1]) == distance(v[i][1], v[i][2]) && distance(v[i][1], v[i][2]) == distance(v[i][0], v[i][2])){
  91.                     cout << "TRIAGOLNIK\n";
  92.                 }
  93.                 else{
  94.                     cout << "NISTO\n";
  95.                 }
  96.             }
  97.         }
  98.         else if(sz == 4){
  99.             da = false;
  100.             sort(v[i].begin(), v[i].end());
  101.             do{
  102.                 a = v[i][0];
  103.                 b = v[i][1];
  104.                 c = v[i][2];
  105.                 d = v[i][3];
  106.                 if(checkIfCordsAreOnTheSameLine(a, b) && checkIfCordsAreOnTheSameLine(b, c) && checkIfCordsAreOnTheSameLine(c, d) && checkIfCordsAreOnTheSameLine(d, a)){
  107.                     if(distance(a, b) == distance(b, c) && distance(b, c) == distance(c, d) && distance(c, d) == distance(d, a)){
  108.                         da = true;
  109.                         break;
  110.                     }
  111.                 }
  112.                 if(da)break;
  113.             }while(next_permutation(v[i].begin(), v[i].end()));
  114.             if(da){
  115.                 cout << "PARALELOGRAM\n";
  116.             }
  117.             else{
  118.                 cout << "NISTO\n";
  119.             }
  120.         }
  121.         else if(sz == 6){
  122.             sort(v[i].begin(), v[i].end());
  123.             da = false;
  124.             do{
  125.                 a = v[i][0];
  126.                 b = v[i][1];
  127.                 c = v[i][2];
  128.                 d = v[i][3];
  129.                 e = v[i][4];
  130.                 f = v[i][5];
  131.                 if(checkIfCordsAreOnTheSameLine(a, b) && checkIfCordsAreOnTheSameLine(b, c) && checkIfCordsAreOnTheSameLine(c, d) && checkIfCordsAreOnTheSameLine(d, e) && checkIfCordsAreOnTheSameLine(e, f) && checkIfCordsAreOnTheSameLine(f, a)){
  132.                     if(distance(a, b) == distance(b, c) && distance(b, c) == distance(c, d) && distance(c, d) == distance(d, e) && distance(d, e) == distance(e, f) && distance(e, f) == distance(f, a)){
  133.                         da = true;
  134.                         break;
  135.                     }
  136.                     if(da)break;
  137.                 }
  138.             }while(next_permutation(v[i].begin(), v[i].end()));
  139.             if(da){
  140.                 cout << "SESTOAGOLNIK\n";
  141.             }
  142.             else{
  143.                 cout << "NISTO\n";
  144.             }
  145.         }
  146.     }
  147.     return 0;
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement