Cod sursa(job #2615836)

Utilizator stanbianca611Stan Bianca stanbianca611 Data 15 mai 2020 17:46:57
Problema Patrate 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <pair>
#define MARJA 1e-4
using namespace std;
int N;//numarul de puncte
vector< pair<double, double> > v;
vector< pair<double, double> > a[20010];
bool compare(pair<double, double> a, pair<double, double> b){
	return (abs(a.first-b.first) <= MARJA && abs(a.second-b.second) <= MARJA);
}
bool functieComparare(pair<double, double> a, pair<double, double> b){
	if(abs(a.first-b.first) <= MARJA){
		return a.second < b.second;
	}
	return a.first < b.first;
}
bool patrat(pair<double, double> a,pair<double, double> b){
	if(a.second<b.second || a.first==b.first){
		return false;//prin conditia asta ma asigur ca punctele nu au aceeasi abscisa
		//si ca b e la dreapta lui a, astfel incat sa fie diametral opuse
	}
	double difAbscisa = b.first-a.first;
	double difOrdonata = b.second-a.second;
	//diferentele le tinem in variabilele astea doua pentru a construi celelalte doua puncte
	pair<double, double> c,d;
	c = make_pair(b.first+difOrdonata, b.second - difAbscisa);
	d = make_pair(a.first+difOrdonata, a.second - difAbscisa);

	bool isSquare = false;
	for(int i=0;i<v[(int)(c.first)+10000].size();i++){
		if(compare(v[(int)(c.first)+10000][i],c)==true){
			isSquare = true;
			break;
		}
	}
	if(isSquare==false)//daca nu am gasit un punct c astfel incat acesta sa poata fi colt al patratului
		return false;
	//repetam ce am facut mai devreme pentru al treilea colt al patratului cu al patrulea colt al sau
	for(int i=0;i<v[(int)(d.first)+10000].size();i++){
		if(compare(v[(int)(d.first)+10000][i],d)==true){
			isSquare = true;
			break;
		}
	}
	return isSquare;//returnam valoarea de adevar, daca am gasit al patrulea colt, o sa devina true, daca l-am gasit pe al treilea, dar pe al patrulea nu, ramane false
}
int main() {
	ifstream fin("patrate3.in");
	ofstream fout("patrate3.out");
	fin>>N;
	v = vector<pair< double, double> > (N);
	for(int i=0;i<N;i++) {
		fin>>v[i].first>>v[i].second;
		a[(int)(v[i].first)+10000].push_back(v[i]);
	}
	sort(v.begin(), v.end(), functieComparare);
	int rez=0;
	for(int i=0;i < N-1;i++){
		for(int j=i+1; j<N;j++){
			if(patrat(v[i],v[j])==true){
				rez++;
			}
		}
	}
	fout<<rez;
	fin.close();
	fout.close();
	return 0;
}
/*

#		*


*       #

*/