记录编号	202534	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm_Def的模拟赛	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.655 s
提交时间	2015-11-01 13:59:17	内存使用	4.19 MiB

#include <cstdio>
#include <cmath> 
#include <algorithm>
using namespace std;
const int kN = 1000+10;
struct Point {
	int x, y;
	Point operator - (const Point & p) const {
		return (Point) {x-p.x, y-p.y};
	}
	bool operator < (const Point & p) const {
		if (x != p.x) return x < p.x;
		return y < p.y;
	}
}ps[kN];
 
int N;
int num[kN][kN];
 
int det(const Point & a, const Point & b) {
	return a.x*b.y - a.y*b.x;
}
 
bool isUnder(const Point & p, const Point & a, const Point & b) {
	return a.x < p.x && p.x <= b.x && det(p-a, b-a) >= 0;
}
 
int calcUnder(int i, int j) {
	int ret = 0;
	for (int k = 1; k <= N; k++) {
		if (isUnder(ps[k], ps[i], ps[j])) ret++;
	}
	return ret;
}
 
int main() {
	// freopen("in.txt", "r", stdin);
	freopen("trib.in", "r", stdin);
	freopen("trib.out", "w", stdout);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		ps[i] = (Point){x, y};
	}
	
	sort(ps+1, ps+1+N);
	for (int i = 1; i <= N; i++) {
		for (int j = i+1; j <= N; j++) {
			num[i][j] = calcUnder(i, j);
		}
	}
	
	int mx = 0, cnt = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = i+1; j <= N; j++) {
			for (int k = j+1; k <= N; k++) {
				int left_p = i, mid_p = j, right_p = k;
				int tmp = 0;
				// 左边垂直 
				if (ps[left_p].x == ps[mid_p].x) {
					tmp = num[mid_p][right_p] - num[left_p][right_p] + 3;
				} else if (ps[mid_p].x == ps[right_p].x) {
					tmp = num[left_p][right_p] - num[left_p][mid_p] + 2;
				} else if (isUnder(ps[mid_p], ps[left_p], ps[right_p])) {
					// 这种mid在left_p, right_p下方，这个时候三个端点都没有被算上 
					tmp = num[left_p][right_p] - num[left_p][mid_p] - num[mid_p][right_p] + 3; 
				} else {
					// mid_p在left_p, right_p的上方，这个时候有一个端点在方案中 
					tmp = num[left_p][mid_p] + num[mid_p][right_p] - num[left_p][right_p] + 2; 
				}
 
				// printf("%d %d %d ans = %d\n", i, j, k, tmp);
				if (tmp > mx) {
					mx = tmp;
					cnt = 1;
				} else if (tmp == mx) {
					cnt++;
				}
			}
		}
	}
	
	/* 
	// 检查是否共线
	for (int i = 1; i <= N; i++) {
		for (int j = i+1; j <= N; j++) {
			for (int k = j+1; k <= N; k++) {
				if (det(ps[i]-ps[k], ps[i]-ps[j]) == 0) {
					printf("wa\n");
				}
			}
		}
	}
	*/
 
	printf("%d\n%d", mx, cnt);
	return 0;
}