为啥n三方跑得飞快
  • 板块P1142 轰炸
  • 楼主BK小鹿
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/10/28 22:54
  • 上次更新2024/10/29 13:44:42
查看原帖
为啥n三方跑得飞快
1345783
BK小鹿楼主2024/10/28 22:54

rt,本来想写个暴力先看看的,结果直接A了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 705;

int n;
int x[N], y[N];

int main()
{
	int ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> x[i] >> y[i];
	for (int i = 1; i <= n; i ++ )
	  for (int j = 1; j <= n; j ++ )
	  {
	  	if (i == j) continue;
	  	 /*
		 y = kx + b;
		 y1 = kx1 + b;
		 k = (y1 - y) / (x1 - x);
		 b = y - kx;
		*/
		int cnt = 2, X1 = x[i], Y1 = y[i], X2 = x[j], Y2 = y[j];
		for (int k = 1; k <= n; k ++ )
		{
			if (k == i || k == j) continue;
			int X = x[k], Y = y[k];
			if ((X2 - X1) * Y == (Y2 - Y1) * X + Y1 * (X2 - X1) - (Y2 - Y1) * X1) cnt ++ ; 
		}
		ans = max(ans, cnt);
	  }
	
	cout << ans << '\n';
	return 0;
}
2024/10/28 22:54
加载中...