Cod sursa(job #2236604)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 august 2018 00:08:17
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MOD 100013
#define DIM 1005*502
#define eps 0.0000001
 
using namespace std;
 
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
struct point{
    double x, y;
}P[1005];

vector <point> H[MOD];
int N,nr;
int SquaresCount;

int cmp(point A, point B){
    if(A.x < B.x)
        return 1;
    if(A.x == B.x && A.y < B.y)
        return 1;
    return 0;
}

int modulo(int number){
    int ans = number % MOD;
    if(ans < 0)
        ans += MOD;
    return ans;
}

int main(){
    fin>>N;
    
    for(int i = 1; i <= N; i ++){
        fin >> P[i].x >> P[i].y;
        int key = P[i].x * 10000;
        key = modulo(key);
        H[key].push_back(P[i]);
    }

    sort(P + 1, P + N + 1, cmp);
    
    for(int i = 1; i < N; i ++)
        for(int j = i + 1; j <= N; j ++){

            point firstPoint, secondPoint;

            point mid;
            mid.x = (P[i].x + P[j].x) / 2.0;
            mid.y = (P[i].y + P[j].y) / 2.0;

            firstPoint.x = mid.x - P[j].y + mid.y;
            firstPoint.y = mid.y + P[j].x - mid.x;

            secondPoint.x = mid.x + P[j].y - mid.y;
            secondPoint.y = mid.y - P[j].x + mid.x;

            int key1 = firstPoint.x * 10000.0;
            key1 = modulo(key1);
            int key2 = secondPoint.x * 10000.0;
            key2 = modulo(key2);

            int found1 = 0, found2 = 0;

            //fout << firstPoint.x << " " << firstPoint.y << "\n";
            for(std::vector<point>::iterator it=H[key1].begin();it!=H[key1].end(); it ++)
                if(abs(it->x - firstPoint.x) < eps && abs(it->y - firstPoint.y) < eps){
                    found1 = 1;
                    break;
                }

            if(!found1)
                continue;

            for(std::vector<point>::iterator it=H[key2].begin();it!=H[key2].end(); it ++)
                if(abs(it->x - secondPoint.x) < eps && abs(it->y - secondPoint.y) < eps){
                    found2 = 1;
                    break;
                }

            if(found2)
                SquaresCount ++;
            // if(found2)
            //     cout << P[i].x << " " << P[i].y << "\n" << P[j].x << " " << P[j].y << "\n" << firstPoint.x << " " << firstPoint.y << "\n" << secondPoint.x << " " << secondPoint.y << "\n";

        }

    fout << SquaresCount / 2 << "\n";
    
}