Cod sursa(job #2310771)

Utilizator richard26Francu Richard richard26 Data 2 ianuarie 2019 00:03:33
Problema Patrate 3 Scor 0
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(int x, int 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;
		else
		{
			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 A.y <= B.y ? 1:0;
		else
		{
			return A.x <= B.x ? 1: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; i++)
	{
		for (j = i + 1; j <= n; j++)
		{
			punct A, B, C, D, mij;
			A.x = v[i].x; A.y = v[i].y;
			B.x = v[j].x; B.y = v[j].y;
			mij.x = (A.x + B.x) / 2.0;
			mij.y = (A.y + B.y) / 2.0;
			D.x=mij.x-v[j].y+mij.y;
            D.y=mij.y+v[j].x-mij.x;
        	C.x=mij.x+v[j].y-mij.y;
        	C.y=mij.y-v[j].x+mij.x;
			if(A.y < B.y)
			{

			}
			if(cb(D) == 1 && cb(C) == 1) nr++;
		}
	}
	
	g<<nr / 2;
	return 0;
}