Cod sursa(job #1276657)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 26 noiembrie 2014 18:23:21
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");

struct point{
	double x, y;
};

const int nmax = 1506;
const double eps = 0.001, r = (double)sqrt(3 * 1.0) * 0.5;
int n, rasp;
point v[nmax];

double modul(double x)
{
	if(x<0)
		return -x;
	else
		return x;
}

bool compar(point a, point b){
    if(modul(a.x - b.x)<eps)
        return a.y<b.y;
	else
		return a.x < b.x;
}

bool verificare(int lo, double x, double y) {
    int hi = n, mid;

    while(lo<=hi)
	{
		mid = (hi + lo) / 2;
        if(modul(v[mid].x - x)<eps)
		{
            if(fabs(v[mid].y - y) < eps)
                return 1;
 
            if(v[mid].y<y)
                lo = mid + 1;
            else
                hi = mid - 1;
 
            continue;
        }
 
        if(v[mid].x<x)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
 
    return 0;
}

int main(){
	int player_unu=0;

	/*for(int i = 1; i<=20000; i++)
	{
		int lim = (int)sqrt(i * 1.0);
		int aux = i * i + i + 1;
		for(int j = 2; j<=lim; j++)
			while(aux%j==0)
				aux /= j;

		if(aux==1)
			out<<i<<'\n';
	}*/

	in>>n;
    for(int i = 1; i <= n; i++)
		in>>v[i].x>>v[i].y;
 
    sort(v + 1, v + n + 1, compar);
 
    for(int i = 1; i<=n; i++)
	{
        for(int j = i + 1; j<=n; j++)
		{
            double xd = v[j].x - v[i].x, yd = v[i].y - v[j].y;
            double xm = (v[i].x + v[j].x) * 0.5, ym = (v[i].y + v[j].y) * 0.5;
 
            if(verificare(j + 1, xm + yd * r, ym + xd * r)==1)
                rasp++;
            if(verificare(j + 1, xm - yd * r, ym - xd * r)==1)
                rasp++;
        }
	}
 
    out<<rasp<<'\n';

	return player_unu;
}