Cod sursa(job #1798948)

Utilizator giotoPopescu Ioan gioto Data 5 noiembrie 2016 16:44:11
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MOD 1000
using namespace std;
int n, Sol;
struct elem{
    double x, y;
}a[1002];
inline bool cmp(elem x, elem y){
    if(x.x != y.x)
        return x.x < y.x;
    if(x.y != y.y)
        return x.y < y.y;
}
inline bool CMP(double x, double y){
    if(abs(x - y) <= 0.00001) return 1;
}
inline bool CBIN(double x, double y){
    int st = 1, dr = n;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(CMP(a[mid].x, x) && CMP(a[mid].y, y))
            return 1;
        if(a[mid].x > x)
            dr = mid - 1;
        else if(a[mid].x < x)
            st = mid + 1;
        else if(a[mid].y < y)
            st = mid + 1;
        else if(a[mid].y > y)
            dr = mid - 1;

    }
    return 0;
}
inline void Solve(double x1, double y1, double x2, double y2){
    double mijx = (x1 + x2) / 2, mijy = (y1 + y2) / 2;
    double dx = abs(mijx - x1), dy = abs(mijy - y1);
    if(y1 < y2){
        double x3 = mijx + dy, y3 = mijy - dx;
        double x4 = mijx - dy, y4 = mijy + dx;
        if(CBIN(x3, y3) == 0) return ;
        if(CBIN(x4, y4) == 0) return ;
        ++Sol; return ;
    }
    double x3 = mijx - dy, y3 = mijy - dx;
    double x4 = mijx + dy, y4 = mijy + dx;
    if(CBIN(x3, y3) == 0) return ;
    if(CBIN(x4, y4) == 0) return ;
    ++Sol; return ;
}

 main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%lf%lf", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n - 3; ++i){
        for(int j = i + 1; j <= n - 2; ++j){
            double x1 = a[i].x, y1 = a[i].y;
            double x2 = a[j].x, y2 = a[j].y;
            Solve(x1, y1, x2, y2);
        }
    }
    printf("%d", Sol);
    return 0;
}