Cod sursa(job #2310777)

Utilizator richard26Francu Richard richard26 Data 2 ianuarie 2019 00:27:32
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
#define N 1001
#define precizie 0.00001

using namespace std;

ifstream f("patrate3.in");
ofstream g("patrate3.out");

int n;

typedef struct 
{
	double x;
	double y;
}punct;

punct v[N];
double mod(double x, double y)
{
	return x > y ? (x - y) : (y - x);
}

int cb(punct A)
{
	int st = 1;
	int dr = n;
	
	while (st <= dr)
	{	
		int mij = (st + dr) / 2;
		if(mod(A.x, v[mij].x) < precizie && mod(A.y, v[mij].y) < precizie)
			return 1;
		
		
			if(mod(v[mij].x, A.x) < precizie)
			{
				if(A.y < v[mij].y) dr = mij - 1;
					else st = mij + 1;
			}
			else
			{
				if(A.x < v[mij].x) dr = mij - 1;
					else st = mij + 1;

			}
	}
	return 0;
}

int cmp(punct A, punct B)
{
	if(A.x<B.x)
    {
   return 1;	
    }
    else if(A.x == B.x && A.y<B.y)	
    {	
        return 1;
    }	
    else
    {
    return 0;
    }
}

int main()
{
	int i, j;
	f>>n;
	for (i = 1; i <= n; i++)
		f>>v[i].x>>v[i].y;
	int nr = 0;
	sort(v + 1, v + n + 1, cmp);
	for (i = 1; i <= n-1; i++)
	{
		for (j = i + 1; j <= n; j++)
		{
		punct A,B,mij;
        mij.x=(v[i].x+v[j].x)/2.0;	
        mij.y=(v[i].y+v[j].y)/2.0;	
        A.x=mij.x-v[j].y+mij.y;	
        A.y=mij.y+v[j].x-mij.x;	
        B.x=mij.x+v[j].y-mij.y;	
        B.y=mij.y-v[j].x+mij.x;	
		if(cb(A) == 1 && cb(B) == 1) nr++;
		}
	}
	
	g<<nr / 2;
	f.close();
	g.close();
	return 0;
}