Cod sursa(job #1481357)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 4 septembrie 2015 11:48:04
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 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():x(0), y(0){}
    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;
    }
    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){
        pct.x = (a[i].x - a[j].x)/2 - (a[i].y - a[j].y)*sqrt3/2;
        pct.y = (a[i].x - a[j].x)*sqrt3/2 + (a[i].y - a[j].y)/2;
        ans += cauta(j+1, n-1);
        pct.x = (a[i].x + a[j].x)/2 + (a[j].y - a[i].y)*sqrt3/2;
        pct.y = -(a[i].x - a[j].x)*sqrt3/2 + (a[i].y - a[j].y)/2 ;
        ans += cauta(j+1, n-1);
    }
    freopen(oname, "w", stdout);
    printf("%d", ans);
    return 0;
}