Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- int n;
- vector<int> v[21];
- vector<int> triangle[301];
- void calculatePascalsTriangle(){
- int nxt = 1;
- int tmp = 1;
- for(int i = 0; i <= 260; i ++){
- for(int j = 0; j < tmp; j ++){
- triangle[i].push_back(nxt);
- nxt ++;
- }
- tmp ++;
- }
- }
- pair<int, int> findCords(int pos){
- int levo = 0;
- int desno = 260;
- int mid, mid2;
- bool da = false;
- int levo2, desno2;
- while(levo <= desno){
- mid = (levo + desno) / 2;
- levo2 = 0;
- desno2 = (int)triangle[mid].size();
- while(levo2 <= desno2){
- mid2 = (levo2 + desno2) / 2;
- if(triangle[mid][mid2] == pos){
- return make_pair(mid, mid2);
- }
- if(triangle[mid][mid2] < pos){
- levo2 = mid2 + 1;
- }
- if(triangle[mid][mid2] > pos){
- desno2 = mid2 - 1;
- }
- }
- if(pos > triangle[mid][(int)triangle[mid].size() - 1]){
- levo = mid + 1;
- }
- else{
- desno = mid - 1;
- }
- }
- return make_pair(-1, -1);
- }
- bool checkIfCordsAreOnTheSameLine(int x, int y){
- pair<int, int> p1 = findCords(x);
- pair<int, int> p2 = findCords(y);
- if(p1.first == p2.first)return true;
- if(p1.first != p2.first && p1.second == p2.second)return true;
- if((p1.first - p2.first) == (p1.second - p2.second))return true;
- return false;
- }
- int distance(int x, int y){
- pair<int, int> p1 = findCords(x);
- pair<int, int> p2 = findCords(y);
- return max(abs(p1.first - p2.first), abs(p1.second - p2.second));
- }
- int main(int argc, const char * argv[]) {
- ios_base::sync_with_stdio(false);
- cin >> n;
- int pos;
- int sz;
- for(int i = 0; i < n; i ++){
- cin >> sz;
- for(int j = 0; j < sz; j ++){
- cin >> pos;
- v[i].push_back(pos);
- }
- }
- calculatePascalsTriangle();
- int a, b, c, d, e, f;
- bool da;
- for(int i = 0; i < n; i ++){
- sz = (int)v[i].size();
- if(sz != 3 && sz != 4 && sz != 6){
- cout << "NISTO\n";
- }
- if(sz == 3){
- if(!checkIfCordsAreOnTheSameLine(v[i][0], v[i][1]) || !checkIfCordsAreOnTheSameLine(v[i][1], v[i][2]) || !checkIfCordsAreOnTheSameLine(v[i][0], v[i][2])){
- cout << "NISTO\n";
- }
- else{
- 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])){
- cout << "TRIAGOLNIK\n";
- }
- else{
- cout << "NISTO\n";
- }
- }
- }
- else if(sz == 4){
- da = false;
- sort(v[i].begin(), v[i].end());
- do{
- a = v[i][0];
- b = v[i][1];
- c = v[i][2];
- d = v[i][3];
- if(checkIfCordsAreOnTheSameLine(a, b) && checkIfCordsAreOnTheSameLine(b, c) && checkIfCordsAreOnTheSameLine(c, d) && checkIfCordsAreOnTheSameLine(d, a)){
- if(distance(a, b) == distance(b, c) && distance(b, c) == distance(c, d) && distance(c, d) == distance(d, a)){
- da = true;
- break;
- }
- }
- if(da)break;
- }while(next_permutation(v[i].begin(), v[i].end()));
- if(da){
- cout << "PARALELOGRAM\n";
- }
- else{
- cout << "NISTO\n";
- }
- }
- else if(sz == 6){
- sort(v[i].begin(), v[i].end());
- da = false;
- do{
- a = v[i][0];
- b = v[i][1];
- c = v[i][2];
- d = v[i][3];
- e = v[i][4];
- f = v[i][5];
- if(checkIfCordsAreOnTheSameLine(a, b) && checkIfCordsAreOnTheSameLine(b, c) && checkIfCordsAreOnTheSameLine(c, d) && checkIfCordsAreOnTheSameLine(d, e) && checkIfCordsAreOnTheSameLine(e, f) && checkIfCordsAreOnTheSameLine(f, a)){
- 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)){
- da = true;
- break;
- }
- if(da)break;
- }
- }while(next_permutation(v[i].begin(), v[i].end()));
- if(da){
- cout << "SESTOAGOLNIK\n";
- }
- else{
- cout << "NISTO\n";
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement