Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<string>
- #include<iostream>
- #include<sstream>
- #include<assert.h>
- #include<cstdio>
- #include<map>
- #include<algorithm>
- #include<bitset>
- #include<cmath>
- #include<queue>
- #include<functional>
- #include<set>
- #include<stack>
- #include<cstdlib>
- #include<cstring>
- using namespace std;
- //=========================================================
- // program:
- //
- int x[8];
- int y[8];
- bool compareDistances(int a, int b, int c, int d)
- {
- //ab = cd ?
- int dx1 = x[a] - x[b];
- int dy1 = y[a] - y[b];
- int dx2 = x[c] - x[d];
- int dy2 = y[c] - y[d];
- return (dx1*dx1 + dy1*dy1 == dx2*dx2 + dy2*dy2);
- }
- bool nonZero(int a, int b)
- {
- //ab = cd ?
- int dx = x[a] - x[b];
- int dy = y[a] - y[b];
- return (dx*dx + dy*dy !=0 );
- }
- bool perpendicularSegments(int a, int b, int c, int d)
- {
- int dx1 = x[a] - x[b];
- int dy1 = y[a] - y[b];
- int dx2 = x[c] - x[d];
- int dy2 = y[c] - y[d];
- return (dy1*dy2 == - dx1*dx2);
- }
- bool paralelSegments(int a, int b, int c, int d)
- {
- int dx1 = x[a] - x[b];
- int dy1 = y[a] - y[b];
- int dx2 = x[c] - x[d];
- int dy2 = y[c] - y[d];
- return (dy1*dx2 == dx1*dy2);
- }
- int area(int a, int b, int c)
- {
- return x[a]*(y[b]-y[c]) + x[b]*(y[c] - y[a]) + x[c]*(y[a] - y[b]);
- }
- bool isRectangle(int * rectangle, bool equalSides = false)
- {
- sort(rectangle, rectangle+4);
- do {
- //possibly not needed.
- if (! nonZero(rectangle[0],rectangle[1]) ) {
- continue;
- }
- if (! nonZero(rectangle[1],rectangle[2]) ) {
- continue;
- }
- if (! nonZero(rectangle[2],rectangle[3]) ) {
- continue;
- }
- if (! nonZero(rectangle[3],rectangle[0]) ) {
- continue;
- }
- // 0-1 =2-3
- if (! compareDistances( rectangle[0],rectangle[1], rectangle[2],rectangle[3]) ) {
- continue;
- }
- // 1-2 = 3-0
- if (! compareDistances( rectangle[2],rectangle[1], rectangle[0],rectangle[3]) ) {
- continue;
- }
- if (equalSides) {
- //0-3 = 3-2
- if (! compareDistances( rectangle[0],rectangle[3], rectangle[2],rectangle[3]) ) {
- continue;
- }
- }
- // make sure segments are perpendicular!
- if ( ! perpendicularSegments( rectangle[0],rectangle[1], rectangle[1],rectangle[2]) ) {
- continue;
- }
- if ( ! perpendicularSegments( rectangle[1],rectangle[2], rectangle[2],rectangle[3]) ) {
- continue;
- }
- if ( ! perpendicularSegments( rectangle[0],rectangle[3], rectangle[2],rectangle[3]) ) {
- continue;
- }
- if ( ! perpendicularSegments( rectangle[0],rectangle[3], rectangle[0],rectangle[1]) ) {
- continue;
- }
- // make sure segments are paralel?
- if (! paralelSegments(rectangle[0],rectangle[1], rectangle[2],rectangle[3]) ) {
- continue;
- }
- if (! paralelSegments(rectangle[1],rectangle[2], rectangle[0],rectangle[3]) ) {
- continue;
- }
- if (area(rectangle[0], rectangle[1], rectangle[2])==0 ) {
- continue;
- }
- if (area(rectangle[0], rectangle[3], rectangle[2])==0 ) {
- continue;
- }
- return true;
- } while (next_permutation(rectangle, rectangle+4));
- }
- bool isSquare(int * square)
- {
- return isRectangle(square, true);
- }
- int square[4];
- int rectangle[4];
- bool solve()
- {
- for (int i=0; i<(1<<8); i++) {
- int sn = 0;
- int rn = 0;
- for (int j=0; j<8; j++) {
- if ( (i & (1<<j ) ) ) {
- square[sn++] = j;
- } else {
- rectangle[rn++] = j;
- }
- }
- if ( (sn==4) && isSquare(square) && isRectangle(rectangle)) {
- return true;
- }
- }
- return false;
- }
- inline void init(){}
- //=========================================================
- // I/O:
- //
- int main()
- {
- while( cin >> x[0] >> y[0] ) {
- for (int i=1; i<8; i++) {
- cin >> x[i] >> y[i];
- }
- if (solve()) {
- cout << "YES"<<endl;
- sort(square,square+4);
- for (int i=0; i<4; i++) {
- if (i) cout << " ";
- cout << (square[i]+1);
- }
- cout << endl;
- sort(rectangle,rectangle+4);
- for (int i=0; i<4; i++) {
- if (i) cout << " ";
- cout << (rectangle[i]+1);
- }
- cout << endl;
- } else {
- cout << "NO" << endl;
- }
- break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment