Guest User

Untitled

a guest
Dec 9th, 2011
459
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.79 KB | None | 0 0
  1. #include<string>
  2. #include<iostream>
  3. #include<sstream>
  4. #include<assert.h>
  5. #include<cstdio>
  6. #include<map>
  7. #include<algorithm>
  8. #include<bitset>
  9. #include<cmath>
  10. #include<queue>
  11. #include<functional>
  12. #include<set>
  13. #include<stack>
  14. #include<cstdlib>
  15. #include<cstring>
  16.  
  17.  
  18. using namespace std;
  19.  
  20. //=========================================================
  21. // program:
  22. //
  23. int x[8];
  24. int y[8];
  25.  
  26. bool compareDistances(int a, int b, int c, int d)
  27. {
  28.     //ab = cd ?
  29.     int dx1 = x[a] - x[b];
  30.     int dy1 = y[a] - y[b];
  31.  
  32.     int dx2 = x[c] - x[d];
  33.     int dy2 = y[c] - y[d];
  34.    
  35.     return (dx1*dx1 + dy1*dy1 == dx2*dx2 + dy2*dy2);
  36. }
  37.  
  38. bool nonZero(int a, int b)
  39. {
  40.     //ab = cd ?
  41.     int dx = x[a] - x[b];
  42.     int dy = y[a] - y[b];
  43.  
  44.     return (dx*dx + dy*dy !=0 );
  45. }
  46.  
  47. bool perpendicularSegments(int a, int b,  int c, int d)
  48. {
  49.     int dx1 = x[a] - x[b];
  50.     int dy1 = y[a] - y[b];
  51.  
  52.     int dx2 = x[c] - x[d];
  53.     int dy2 = y[c] - y[d];
  54.     return (dy1*dy2 == - dx1*dx2);    
  55. }
  56. bool paralelSegments(int a, int b,  int c, int d)
  57. {
  58.     int dx1 = x[a] - x[b];
  59.     int dy1 = y[a] - y[b];
  60.  
  61.     int dx2 = x[c] - x[d];
  62.     int dy2 = y[c] - y[d];
  63.     return (dy1*dx2 == dx1*dy2);    
  64. }
  65.  
  66. int area(int a, int b, int c)
  67. {
  68.     return x[a]*(y[b]-y[c]) + x[b]*(y[c] - y[a]) + x[c]*(y[a] - y[b]);
  69. }
  70.  
  71. bool isRectangle(int * rectangle, bool equalSides = false)
  72. {
  73.     sort(rectangle, rectangle+4);
  74.    
  75.    
  76.    
  77.     do {
  78.         //possibly not needed.
  79.        
  80.        
  81.         if (! nonZero(rectangle[0],rectangle[1]) ) {
  82.             continue;
  83.         }
  84.         if (! nonZero(rectangle[1],rectangle[2]) ) {
  85.             continue;
  86.         }
  87.         if (! nonZero(rectangle[2],rectangle[3]) ) {
  88.             continue;
  89.         }
  90.         if (! nonZero(rectangle[3],rectangle[0]) ) {
  91.             continue;
  92.         }
  93.         // 0-1 =2-3
  94.         if (! compareDistances( rectangle[0],rectangle[1], rectangle[2],rectangle[3]) ) {
  95.             continue;
  96.         }
  97.         // 1-2 = 3-0
  98.         if (! compareDistances( rectangle[2],rectangle[1], rectangle[0],rectangle[3]) ) {
  99.             continue;
  100.         }
  101.  
  102.        
  103.         if (equalSides) {
  104.             //0-3 = 3-2
  105.             if (! compareDistances( rectangle[0],rectangle[3], rectangle[2],rectangle[3]) ) {
  106.                 continue;
  107.             }
  108.         }
  109.  
  110.         // make sure segments are perpendicular!
  111.         if ( ! perpendicularSegments( rectangle[0],rectangle[1],  rectangle[1],rectangle[2]) ) {
  112.             continue;
  113.         }
  114.         if ( ! perpendicularSegments( rectangle[1],rectangle[2],  rectangle[2],rectangle[3]) ) {
  115.             continue;
  116.         }
  117.         if ( ! perpendicularSegments( rectangle[0],rectangle[3],  rectangle[2],rectangle[3]) ) {
  118.             continue;
  119.         }
  120.         if ( ! perpendicularSegments( rectangle[0],rectangle[3],  rectangle[0],rectangle[1]) ) {
  121.             continue;
  122.         }
  123.        
  124.         // make sure segments are paralel?
  125.        
  126.         if (! paralelSegments(rectangle[0],rectangle[1],  rectangle[2],rectangle[3]) ) {
  127.             continue;
  128.         }
  129.         if (! paralelSegments(rectangle[1],rectangle[2],  rectangle[0],rectangle[3]) ) {
  130.             continue;
  131.         }
  132.        
  133.         if (area(rectangle[0], rectangle[1], rectangle[2])==0 ) {
  134.             continue;
  135.         }
  136.         if (area(rectangle[0], rectangle[3], rectangle[2])==0 ) {
  137.             continue;
  138.         }
  139.    
  140.         return true;
  141.        
  142.     } while (next_permutation(rectangle, rectangle+4));
  143. }
  144.  
  145. bool isSquare(int * square)
  146. {
  147.     return isRectangle(square, true);
  148. }
  149.  
  150. int square[4];
  151. int rectangle[4];
  152.  
  153. bool solve()
  154. {
  155.     for (int i=0; i<(1<<8); i++) {
  156.         int sn = 0;
  157.         int rn = 0;
  158.         for (int j=0; j<8; j++) {
  159.             if ( (i & (1<<j ) ) ) {
  160.                 square[sn++] = j;
  161.             } else {
  162.                 rectangle[rn++] = j;
  163.             }
  164.         }
  165.         if ( (sn==4) && isSquare(square) && isRectangle(rectangle)) {
  166.             return true;
  167.         }
  168.     }
  169.     return false;
  170. }
  171.  
  172. inline void init(){}
  173. //=========================================================
  174. // I/O:
  175. //
  176. int main()
  177. {
  178.     while( cin >> x[0] >> y[0] ) {
  179.         for (int i=1; i<8; i++) {
  180.             cin >> x[i] >> y[i];
  181.         }
  182.         if (solve()) {
  183.             cout << "YES"<<endl;
  184.             sort(square,square+4);
  185.             for (int i=0; i<4; i++) {
  186.                 if (i) cout << " ";
  187.                 cout << (square[i]+1);
  188.             }
  189.             cout << endl;
  190.             sort(rectangle,rectangle+4);
  191.             for (int i=0; i<4; i++) {
  192.                 if (i) cout << " ";
  193.                 cout << (rectangle[i]+1);
  194.             }
  195.             cout << endl;
  196.         } else {
  197.             cout << "NO" << endl;
  198.         }
  199.         break;
  200.     }
  201.     return 0;
  202. }
  203.  
Advertisement
Add Comment
Please, Sign In to add comment