Submission #44919

---

Source Code Expand

#include <iostream>

#ifdef __DEBUG
#define TRACE(var) std::clog << #var << ':' << ' ' << var << std::endl
#else
#define	TRACE(var)
#endif

struct Vector{
	int x;
	int y;
};

#ifdef __DEBUG
inline std::ostream& operator<<(std::ostream& left, Vector const& right){
	left << '(' << right.x << ',' << ' ' << right.y << ')';
	return left;
}
#endif

inline void simplify(Vector* vec){
	int m = ((*vec).x > 0 ? (*vec).x : -(*vec).x);
	int n = ((*vec).y > 0 ? (*vec).y : -(*vec).y);
	if(m < n){
		std::swap(m, n);
	}
	TRACE(m);
	TRACE(n);
	while(n != 0){
		int tmp = n;
		n = m % n;
		m = tmp;
	}
	(*vec).x /= m;
	(*vec).y /= m;
}

inline Vector direction_vector(Vector const& p1, Vector const& p2){
	Vector res = {p2.x - p1.x, p2.y - p1.y};
	simplify(&res);
	return res;
}

inline void vec_insert(int const& i, Vector* vec, Vector const& val){
	int idx = -1;
	while(++idx < i){
		if(vec[idx].x > val.x || (vec[idx].x == val.x && vec[idx].y > val.y)){
			int t = i;
			do{
				vec[t] = vec[t - 1];
				t--;
			}while(t > idx);
			break;
		}
	}
	vec[idx] = val;
}

inline void find(unsigned long long int& res, bool panel[100][100], Vector const& a, Vector const& b, Vector const& ab){
	Vector current;
	Vector increm;
	if(ab.x > 0 || (ab.x == 0 && ab.y > 0)){
		current = b;
		increm = ab;
	}else{
		current = a;
		increm.x = -ab.x;
		increm.y = -ab.y;
	}
	TRACE(increm);
	do{
		TRACE(current);
		current.x += increm.x;
		current.y += increm.y;
		if(current.x >= 100  || current.y < 0 || current.x < 0 || current.y >= 100){
			break;
		}
		if(panel[current.x][current.y]){
			res--;
			TRACE(res);
		}
	}while(true);
}

int main(void){
	int n;
	unsigned long long int res = 0;
	Vector vec[10000];
	bool panel[100][100];
	for(int i = 0; i < 100; i++){
		for(int j = 0; j < 100; j++){
			panel[i][j] = false;
		}
	}

	std::cin >> n;

	for(int i = 0; i < n; i++){
		Vector tmp;
		std::cin >> tmp.x >> tmp.y;
		panel[tmp.x][tmp.y] = true;
		vec_insert(i, vec, tmp);
	}

#ifdef __DEBUG
	for(int i = 0; i < n; i++){
		std::cout << '(' << vec[i].x << ',' << ' ' << vec[i].y << ')' << ',' << ' ';
	}
	std::cout << std::endl;
	system("pause");
	std::cout << std::endl;
	for(int i = 0; i < 100; i++){
		for(int j = 0; j < 100; j++){
			std::cout << (panel[i][j] ? '*' : '+');
		}
		std::cout << std::endl;
	}
	system("pause");
#endif
	
	for(int i = 0; i < n - 3; i++){
		TRACE(i);
		for(int j = i + 1; j < n - 2; j++){
			TRACE(j);
			Vector ij = direction_vector(vec[i], vec[j]);
			TRACE(ij);
			for(int k = j + 1; k < n - 1; k++){
				TRACE(k);
				Vector ik = direction_vector(vec[i], vec[k]);
				TRACE(ik);
				if(ij.x == ik.x && ij.y == ik.y || ij.x == -ik.x && ij.y == -ik.y){
					continue;
				}
				Vector jk = direction_vector(vec[j], vec[k]);
				TRACE(jk);
				res += n - k - 1;
				find(res, panel, vec[i], vec[j], ij);
				find(res, panel, vec[i], vec[k], ik);
				find(res, panel, vec[j], vec[k], jk);
			}
		}
	}

	std::cout << res % 1000000007 << std::endl;

#ifdef __DEBUG
	system("pause");
#endif

	return 0;
}

Submission Info

Judge Result