Code Forces beta round 97 div 2 Problem D

BetterSolution.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

vector <pair <int,int> > points;
vector <int> ans;

vector < pair<int, int> > getVectors(int a, int b,  int c, int d){
	int x [4];
	int y [4];
	x[0] = points[a].first; y[0] = points[a].second;
	x[1] = points[b].first; y[1] = points[b].second;
	x[2] = points[c].first; y[2] = points[c].second;
	x[3] = points[d].first; y[3] = points[d].second;
	
	vector <pair <int, int> > v;
	for (int i = 0; i < 4; i++){
		int next = (i + 1) % 4;
		v.push_back (make_pair(x[next] - x[i],  y[next] - y[i]));
	}
	
	return v;
}

bool rectangle(int a, int b, int c, int d){
	//Get the vectors of the sides of the "rectangle"
	vector <pair <int, int> > v = getVectors(a, b, c, d);
	
	for (int i = 0; i < 4; i++){
		// Perpendicular if dot product of contiguous vectors is 0
		int next = (i + 1) % 4;
		if (1LL * v[i].first * v[next].first + 1LL * v[i].second * v[next].second != 0){
			return false;
		}
	}	
	return true;
}


bool square(int a, int b, int c, int d){
	
	if (rectangle(a, b, c, d)){
		//Get the vectors of the sides of the "square"
		vector <pair <int, int> > v = getVectors(a, b, c, d);
				
		// All vectors (sides) have the same magnitude (length)
		long long length = 1LL * v[0].first * v[0].first + 1LL * v[0].second * v[0].second;
		for (int i = 0; i < 4; i++){
			long long length2 = 1LL * v[i].first * v[i].first + 1LL * v[i].second * v[i].second;
			if (length2 != length){
				return false;
			}
		}
		return true;
	}else{		
		return false;
	}
}

void print(){
	for (int i = 0; i < 4; i++){
		cout << ans[i] + 1;
		if (i < 3) cout << " ";
	}	
	cout << endl;
	for (int i = 4; i < 8; i++){
		cout << ans[i] + 1;
		if (i < 7) cout << " ";
	}		
	cout << endl;
}

bool solve(){
	// Check all the possible permutations and see if any of them is a solution
	do{	
		if ((square(ans[0],ans[1],ans[2],ans[3])) and (rectangle(ans[4],ans[5],ans[6],ans[7]))){
			return true;
		}
	}while(next_permutation(ans.begin(), ans.end()));
	// No permutation was a solution
	return false;
}

int main(){
	// Read input
	for (int i = 0; i < 8; i++){
		int x, y;
		cin >> x >> y;
		points.push_back(make_pair(x,y));
		ans.push_back(i);
	}
	// Solve
	if (solve()){
		puts("YES");
		print();
	}else{
		puts("NO");
	}
	
    return 0;
}

InitialSolution.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

vector <pair <int,int> > points;
vector <int> ans;

bool rectangle(int a, int b, int c, int d){
	int x [4];
	int y [4];
	x[0] = points[a].first; y[0] = points[a].second;
	x[1] = points[b].first; y[1] = points[b].second;
	x[2] = points[c].first; y[2] = points[c].second;
	x[3] = points[d].first; y[3] = points[d].second;
	
	
	vector <pair <int, int> > v;
	for (int i = 0; i < 4; i++){
		int next = (i + 1) % 4;
		v.push_back (make_pair(x[next] - x[i],  y[next] - y[i]));
	}
	for (int i = 0; i < 4; i++){
		// dot product = 0
		int next = (i + 1) % 4;
		if (1LL * v[i].first * v[next].first + 1LL * v[i].second * v[next].second != 0){
			return false;
		}
	}
	
	return true;
}


bool square(int a, int b, int c, int d){
	
	if (rectangle(a, b, c, d)){
		int x [4];
		int y [4];
		x[0] = points[a].first; y[0] = points[a].second;
		x[1] = points[b].first; y[1] = points[b].second;
		x[2] = points[c].first; y[2] = points[c].second;
		x[3] = points[d].first; y[3] = points[d].second;

		vector <pair <int, int> > v;

		for (int i = 0; i < 4; i++){
			int next = (i + 1) % 4;
			v.push_back (make_pair(x[next] - x[i],  y[next] - y[i]));
		}
		
		long long length = 1LL * v[0].first * v[0].first + 1LL * v[0].second * v[0].second;
		for (int i = 0; i < 4; i++){
			long long length2 = 1LL * v[i].first * v[i].first + 1LL * v[i].second * v[i].second;
			if (length2 != length){
				return false;
			}
		}
		return true;
	}
	return false;
}

bool solve(){
	do{	
		if ((square(ans[0],ans[1],ans[2],ans[3])) and (rectangle(ans[4],ans[5],ans[6],ans[7]))){
			return true;
		}
	}while(next_permutation(ans.begin(), ans.end()));
	return false;
}

int main(){
	
	for (int i = 0; i < 8; i++){
		int x, y;
		cin >> x >> y;
		points.push_back(make_pair(x,y));
		ans.push_back(i);
	}
	if (solve()){
		puts("YES");
		for (int i = 0; i < 8; i++){
			cout << ans[i] + 1;
			if (i < 7 and 1 != 3) cout << " ";
			if (i == 3) cout << endl;
		}
		cout << endl;
	}else{
		puts("NO");
	}
	
    return 0;
}