Pagini recente » Cod sursa (job #2616247) | Cod sursa (job #4693) | Cod sursa (job #2163347) | Cod sursa (job #2687483) | Cod sursa (job #2615836)
#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;
}
/*
# *
* #
*/