Cod sursa(job #2202092)

Utilizator Claudiu07Pana Claudiu Claudiu07 Data 7 mai 2018 15:31:25
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
const double EPS = 1e-12;
int N,ans;
struct punct
{
    double x,y;
} v[1002];
bool cmp(double A, double B)
{
    return abs(A-B)<EPS;
}
bool cmpp(punct A, punct B)
{
    if (cmp(A.x, B.x)==1)
        return A.y<B.y;
    return A.x<B.x;
}
int cb(punct a)
{
    int p=1, u=N;
    while(p<=u)
    {
        int m=(p+u)/2;
        if(cmp(v[m].x,a.x) && cmp(v[m].y, a.y)) return 1;
        if (cmp(v[m].x, a.x)==1)
        {
            if (v[m].y<a.y)
                p=m+1;
            else
                u=m-1;
        }
        else
        {
            if (v[m].x<a.x)
                p=m+1;
            else
                u=m-1;
        }
    }
    return 0;
}
void sol()
{
    for (int i=1; i<N; i++)
        for (int j=i+1; j<=N; j++)
        {
            punct M, A, B;

            M.x=(v[i].x+v[j].x)/2;
            M.y=(v[i].y+v[j].y)/2;

            A.x=M.x-(v[j].y-M.y);
            A.y=M.y+(v[j].x-M.x);

            B.x=M.x+(v[j].y-M.y);
            B.y=M.y-(v[j].x-M.x);

            if (cb(A)==1 && cb(B)==1)
                ans++;
        }
    ans/=2;
}
int main()
{
    f>>N;
    for(int i=1; i<=N; i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+N+1,cmpp);
    sol();
    g<<ans;
    return 0;
}