Cod sursa(job #2878602)

Utilizator alextmAlexandru Toma alextm Data 27 martie 2022 12:57:26
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int,int> point;

const int MAXN = 1505;
const double EPS = 0.001;

const double COS60 = 0.5;
const double SIN60 = 0.86602540378;

int nr, n;
point v[MAXN];

bool cmp(point A, point B) {
	return A.x < B.x || (fabs(A.x - B.x) < EPS && A.y < B.y);
}

void findPosition(double xc, double yc) {
	int st = 1, dr = n;
	while(st <= dr) {
		int mid = (st + dr) / 2;
		if(fabs(v[mid].x - xc) < EPS && fabs(v[mid].y - yc) < EPS) {
			nr++;
			return;
		}
		
		if(v[mid].x > xc || (fabs(v[mid].x - xc) < EPS && v[mid].y > yc))
			dr = mid - 1;
		else
			st = mid + 1;
	}
}

int main() {
	double x3, y3;
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i].x >> v[i].y;
	sort(v + 1, v + n + 1, cmp);
	
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++) {
			int trX = v[j].x - v[i].x;
			int trY = v[j].y - v[i].y;
			
			x3 = v[i].x + COS60 * trX - SIN60 * trY;
			y3 = v[i].y + SIN60 * trX + COS60 * trY;
			findPosition(x3, y3);
			
			x3 = v[i].x + COS60 * trX + SIN60 * trY;
			y3 = v[i].y - SIN60 * trX + COS60 * trY;
			findPosition(x3, y3);
		}
		
	cout << nr / 3 << '\n';
	
	return 0;
}