Cod sursa(job #1986739)

Utilizator andreistanStan Andrei andreistan Data 28 mai 2017 20:43:45
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
const double EPS=1e-5;

struct punct
{
    double x,y;
};

int N;
punct v[1001];

int egal(double a, double b)
{
    double d = a - b;
    if(d < -EPS)return -1;
    if(d > +EPS)return 1;
    return 0;
}

int egal(const punct &A, const punct &B)
{
    int ex = egal(A.x, B.x);
    int ey = egal(A.y, B.y);
    if(ex == 0) return ey;
    return ex;
}

void patrat2p_diag(punct M1, punct M2, punct &A, punct &B)
{
    punct M0;
    M0.x = (M1.x+M2.x)/2;
    M0.y = (M1.y+M2.y)/2;
    A.x = M0.x - M2.y + M0.y;
    A.y = M0.y + M2.x - M0.x;
    B.x = M0.x + M2.y - M0.y;
    B.y = M0.y - M2.x + M0.x;
}

int comp(const void *a, const void *b)
{
    double dif=(*(punct*)a).x - (*(punct*)b).x;
    if(dif==0)
    {
        dif=(*(punct*)a).y - (*(punct*)b).y;
        if(dif>0)return 1;
        return -1;
    }
    if(dif>0)return 1;
    return -1;
}

bool cautbin(punct P)
{
    int st = 1, dr = N;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        int e = egal(v[mij], P);
        if(e == 0)
            return 1;
        if(e == 1)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    return 0;
}

int main()
{
    int nrp=0;
    f>>N;
    for(int i=1; i<=N; i++)
        f>>v[i].x>>v[i].y;
    qsort(v+1,N,sizeof(punct),comp);
    for(int i=1; i<N; i++)
        for(int j=i+1; j<=N; j++)
        {
            punct A,B;
            patrat2p_diag(v[i],v[j],A,B);
            if(cautbin(A) && cautbin(B))
                nrp++;
        }
    g<<nrp/2;
    return 0;
}