Cod sursa(job #1479720)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 1 septembrie 2015 00:35:02
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_set>
#include <cmath>
using namespace std;

constexpr double epsilon = 1e-3;

double eq(const double a, const double b){
	return (a < b) ? b-a <= epsilon : a-b <= epsilon; }

double rnd(const double x){
	return x < 0 ? -rnd(-x) : floor(x + 0.5); }

struct point{
	double x, y;
	constexpr point(): x(0), y(0){}
	point(const double X, const double Y):
		x(X), y(Y){}
	bool operator==(const point& rhs)const{
		return eq(x, rhs.x) && eq(y, rhs.y); }
	bool operator<(const point& rhs)const{
		return !eq(x, rhs.x) ? x < rhs.x :
			!eq(y, rhs.y) && y < rhs.y; } };

ostream& operator<<(ostream& lhs, const point& rhs){
	lhs << rhs.x << ' ' << rhs.y;
	return lhs; }

namespace std{
	template <>
	struct hash<point>{
		size_t operator()(const point& p)const{
			hash<double> hs;
			return hs(p.x) << 3 + hs(p.y); } }; }

constexpr double PI = 3.14159265358979323846;

pair<point, point> make_pts(const point a, const point b){
	point r(b.x - a.x, b.y - a.y);
	const double theta = atan2(r.y, r.x);
	double theta1 = theta + PI/3, theta2 = theta - PI/3;
	if(theta1 >= 2*PI){
		theta1 -= 2*PI; }
	if(theta2 < 0){
		theta2 += 2*PI; }
	const double distance = sqrt(r.x*r.x + r.y*r.y);	
	return { point(a.x + cos(theta1) * distance, a.y + sin(theta1) * distance),
		point(a.x + cos(theta2) * distance, a.y + sin(theta2) * distance)} ; }

int main(){
	ifstream f("triang.in");
	ofstream g("triang.out");
	int n;
	f >> n;
	vector<point> puncte;
	puncte.reserve(n);
	for(int i = 0; i < n; ++i){
		double x, y;
		f >> x >> y;
		puncte.emplace_back(x, y); }
	sort(begin(puncte), end(puncte));
	int rez = 0;
	for(int i = 0; i+2 < n; ++i){
		for(int j = 0; j+1 < n; ++j){
			if(i != j){
				const auto pts = make_pts(puncte[i], puncte[j]);
				if(binary_search(begin(puncte) + j + 1, end(puncte), pts.first)){
					++rez; }
				if(binary_search(begin(puncte) + j + 1, end(puncte), pts.second)){
					++rez; } } } }
	g << rez;
	return 0; }