Cod sursa(job #1481361)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 4 septembrie 2015 12:01:19
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const char iname[] = "triang.in";
const char oname[] = "triang.out";
const int MAXN = 1505;
double myabs(double x){
    return x >= 0 ? x : -x;
}
struct Punct{
    double x;
    double y;
    Punct(double xx = 0, double yy = 0):x(xx), y(yy){}
    bool operator=(const Punct &c){
        if(this != &c){
            x = c.x;
            y = c.y;
            return true;
        }
        return false;
    }
    bool operator<(const Punct &c){
        if(x < c.x) return true;
        else if(x == c.x){
            if(y < c.y) return true;
            else return false;
        }
        else return false;
    }
    bool operator==(const Punct &c){
        if(myabs(x - c.x) < 1e-7 && myabs(y - c.y) < 1e-7)
            return true;
        return false;
    }
    Punct operator-(const Punct&c){
        return Punct(x-c.x, y-c.y);
    }
    Punct operator+(const Punct&c){
        return Punct(x+c.x, y+c.y);
    }
    friend ostream& operator<<(ostream& out, const Punct&);
};

ostream& operator<<(ostream& out, const Punct& c){
        out << "x=" << c.x << " " << "y=" << c.y;
        return out;
    }
int n;
Punct a[MAXN],b[MAXN], pct;

void merge_sort(int st, int dr){
    if(st != dr){
        int mid = st + ((dr-st)>>1);
        merge_sort(st, mid);
        merge_sort(mid+1, dr);
        for(int i = st, k = st, j = mid+1; (j<=dr)||(i<=mid);){
            if(j>dr || ((i <= mid) && (a[i]<a[j])))
                b[k++] = a[i++];
            else
                b[k++] = a[j++];
        }
        for(int i = st; i <= dr; ++i)
            a[i] = b[i];
    }
}

void read(){
    freopen(iname, "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%lf %lf", &(a[i].x), &(a[i].y));
}

int cauta(int st, int dr){
    while(st <= dr){
        int mid = st + (dr - st)/2;
        if(a[mid] == pct) return 1;
        else if(a[mid] < pct) st = mid+1;
        else dr = mid-1;
    }
    return 0;
}

int main()
{

    read();
    merge_sort(0,n-1);
    double sqrt3 = sqrt(3);
    int ans = 0;
    for(int i = 0; i < n-2; ++i)
    for(int j = i+1; j < n-1; ++j){
        Punct v = a[j]-a[i];
        Punct v1;
        v1.x = v.x/2 - v.y*sqrt3/2;
        v1.y = v.x*sqrt3/2 + v.y/2;
        pct = v1+a[i];
        ans += cauta(j+1, n-1);
        v1.x = v.x/2 + v.y*sqrt3/2;
        v1.y = v.y/2 - v.x*sqrt3/2;
        pct = v1 + a[i];
        ans += cauta(j+1, n-1);
    }
    freopen(oname, "w", stdout);
    printf("%d", ans);
    return 0;
}