Cod sursa(job #1748492)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 26 august 2016 13:44:17
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 1550

using namespace std;

const double EPS = 0.0001;
inline bool equals(double e, double f)
{
    return e-f >= -EPS && e-f <= EPS;
}

struct coord
{
    double x, y;
    coord(double x = -50000, double y = -50000) : x(x), y(y) { }
    bool operator()(coord e, coord f)
    {
        if (!equals(e.x, f.x)) return e.x < f.x;
        return e.y < f.y;
    }
};
coord a[MAXN];
int n;

void citire()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf %lf\n", &a[i].x, &a[i].y);
	sort(a+1, a+n+1, coord());
}

int exista(double x, double y)
{
    int ind = 0, step;
    for (step = 1; step < n; step <<= 1);
    for (step; step; step >>= 1) {
        if (ind + step <= n && a[ind+step].x <= x+EPS)
			ind += step;
    }
    for (step = 1; step < n; step <<= 1);
    for (step; step; step >>= 1) {
        if (ind + step <= n && equals(a[ind+step].x, x) && a[ind+step].y <= y+EPS)
			ind += step;
    }
    int f = equals(a[ind].x, x) && equals(a[ind].y, y);
    f |= equals(a[ind].x, x) && equals(a[ind+1].y, y);
    return f;
}

void solve()
{
	int rez = 0;
    for (int i = 1; i < n; i++)
	{
        coord p = a[i];
        for (int j = i+1; j <= n; j++) {
			coord q = a[j];
            double D = sqrt((q.y-p.y)*(q.y-p.y) + (q.x-p.x)*(q.x-p.x));
            double msl = (q.x - p.x) / (q.y-p.y);
            double dx = (q.x-p.x)/2;
            double dy = (p.y-q.y)/2;
            double x1 = (p.x+q.x)/2 + dy * sqrt(3.0);
            double y1 = (p.y+q.y)/2 + dx * sqrt(3.0);
            double x2 = (p.x+q.x)/2 - dy * sqrt(3.0);
            double y2 = (p.y+q.y)/2 - dx * sqrt(3.0);
			rez += exista(x1, y1);
			rez += exista(x2, y2);
        }
	}
	printf("%d", rez/3);
}

int main()
{
	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);

	citire();
	solve();

    return 0;
}