Cod sursa(job #8319)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 24 ianuarie 2007 14:39:26
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#define NMAX 1010
#define eps 0.00001

using namespace std;

vector<pair<double, double> > P;
int N, Num;

int cb(double xc, double yc)
{
        int mij, p1, p2;
        double x, y;

        for (p1 = 0, p2 = N-1, mij = (p1+p2)/2; p1 <= p2; mij = (p1+p2)/2)
        {
                x = P[mij].first;
                y = P[mij].second;
                if (fabs(x-xc) < eps && fabs(y-yc) < eps) return 1;
                if (x-xc > eps || (fabs(x-xc) < eps && y-yc > eps)) p2 = mij-1;
                else p1 = mij+1;
        }
        return 0;
}

int main()
{
        double xm, ym, x3, y3, x4, y4, dx, dy, d1, d2, d3;
        int i, j, ok;

        freopen("patrate3.in", "r", stdin);
        scanf("%d", &N);
        for (i = 0; i < N; i++)
        {
                scanf("%lf %lf", &dx, &dy);
                P.push_back(make_pair(dx, dy));
        }

        sort(P.begin(), P.end());

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                xm = (P[i].first+P[j].first)/2.0;
                ym = (P[i].second+P[j].second)/2.0;
                dx = fabs(xm-P[i].first);
                dy = fabs(ym-P[j].second);
                if (P[i].second <= P[j].second)
                {
                        x3 = xm+dy;
                        y3 = ym-dx;
                        x4 = xm-dy;
                        y4 = ym+dx;
                }
                else
                {
                        x3 = xm-dy;
                        y3 = ym-dx;
                        x4 = xm+dy;
                        y4 = ym+dx;
                }
                d1 = (x3-P[i].first)*(x3-P[i].first)+(y3-P[i].second)*(y3-P[i].second);
                d2 = (x3-P[j].first)*(x3-P[j].first)+(y3-P[j].second)*(y3-P[j].second);
                d3 = (P[j].first-P[i].first)*(P[j].first-P[i].first)+(P[j].second-P[i].second)*(P[j].second-P[i].second);
                if (fabs(d1+d2-d3) < eps)
                {
                   ok = 0;
                   ok += cb(x3, y3);
                   ok += cb(x4, y4);
                   Num += (ok==2);
                   if (ok == 2)
                      ok = 0;
                }
               }

        freopen("patrate3.out", "w", stdout);
        printf("%d\n", Num/2);

        return 0;
        
}