Cod sursa(job #1592238)

Utilizator razvandRazvan Dumitru razvand Data 7 februarie 2016 12:49:39
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream in("triang.in");
ofstream out("triang.out");

const double sin60 = sin(60*M_PI/180);
const double cos60 = cos(60*M_PI/180);
const double sin60N = sin(-60*M_PI/180);
const double cos60N = cos(-60*M_PI/180);

struct p {
    double x;
    double y;
};

int n;
p v[1501];
p t;

bool eq(double a, double b) {

    return ((int)a*1000) == ((int)b*1000);

}

p rot60(p p1, p p2) {

    int mult = 1;
    if(p2.y < p1.y)
        mult *= -1;

    t.x = p1.x + (p2.x - p1.x) * cos60 - (p2.y - p1.y) * mult * sin60;
    t.y = p1.y + (p2.x - p1.x) * sin60 + (p2.y - p1.y) * mult * cos60;

    return t;

}
p rot60N(p p1, p p2) {

    int mult = 1;
    if(p2.y < p1.y)
        mult *= -1;

    t.x = p1.x + (p2.x - p1.x) * cos60N - (p2.y - p1.y) * mult * sin60N;
    t.y = p1.y + (p2.x - p1.x) * sin60N + (p2.y - p1.y) * mult * cos60N;

    return t;

}

bool cmp(p t1, p t2) {
    if(t1.x == t2.x)
        return t1.y < t2.y;
    return t1.x < t2.x;
}

bool caut(p t1, int st, int dr) {

    int mid = (st+dr)/2;

    if(st >= dr)
        return false;

    if(eq(v[mid].x, t1.x) && eq(v[mid].y, t1.y))
        return true;

    if(v[mid].x > t1.x)
        return caut(t1, st, mid-1);
    if(v[mid].x < t1.x)
        return caut(t1, mid+1, dr);

    if(v[mid].y > t1.y)
        return caut(t1, st, mid-1);
    if(v[mid].y < t1.y)
        return caut(t1, mid+1, dr);

    //return true;

}

int main() {

    in >> n;

    double sq = 1.7320508;

    setprecision(7);
    in.precision(4);

    for(int i = 0; i < n; i++) {
        in >> t.x >> t.y;
        v[i] = t;
    }

    sort(v, v+n, cmp);

    /*for(int i = 0; i < n; i++) {

        cout << v[i].x << " " << v[i].y << endl;

    }*/

    long long rez = 0;

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {

            p t2 = rot60(v[i], v[j]);
            p t3 = rot60N(v[i], v[j]);

            /*cout << v[i].x << " " << v[i].y << "  " << v[j].x << " " << v[j].y << endl;
            cout << t2.x << " " << t2.y << endl;
            cout << t3.x << " " << t3.y << endl << endl;*/

            rez += caut(t2, 0, n);
            rez += caut(t3, 0, n);

            //double p1 =

            //cout << "(" << v1[i] << ", " << v2[i] << ") (" << v1[j] << ", " << v2[j] << ") -> " << "(" << hF11 << ", " << hF12 << ") (" << hF21 << ", " << hF22 << ")" << endl;

        }
    }

    out << rez;

    return 0;

}