企业官网建设流程全解析

P1142 轰炸

网页链接

P1142 轰炸

题目描述

“我该怎么办？”飞行员 klux 向你求助。

事实上，klux 面对的是一个很简单的问题，但是他实在太菜了。

klux 要想轰炸某个区域内的一些地方，它们是位于平面上的一些点，但是（显然地）klux 遇到了抵抗，所以 klux 只能飞一次，而且由于飞机比较破，一但起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸最多的地方。

输入格式

第一行一个整数n nn。

接下来n nn行，每行有一对整数，表示一个点的坐标。没有一个点会出现两次。

输出格式

一个整数，表示一条直线能覆盖的最多的点数。

输入输出样例 #1

输入 #1

5 1 1 2 2 3 3 9 10 10 11

输出 #1

3

说明/提示

数据范围

对于全部数据，保证1 ≤ n ≤ 700 1\le n\le 7001≤n≤700。

本题翻译并改编自 uva270，数据及解答由 uva 提供。

解题思路

本题核心是枚举直线+向量叉积共线判断，求解平面上最多点共线的数量。给定数据范围n ≤ 700 n \le 700n≤700，采用三重循环暴力枚举所有直线：固定两个点确定唯一直线，遍历剩余所有点，利用向量叉积判断点是否在该直线上，该方法完全避免浮点运算，无精度误差。统计每条直线上的总点数，实时更新全局最大值。若点数n ≤ 1 n \le 1n≤1，直接返回对应结果。算法时间复杂度为O ( n 3 ) O(n^3)O(n3)，在题目数据规模下计算量合理，简洁直观且精准高效。

总结

核心逻辑：枚举任意两点确定直线，判断所有点是否共线，统计最大点数。
关键操作：使用向量叉积公式判断三点共线，规避浮点精度问题。
效率保障：暴力枚举适配n ≤ 700 n \le 700n≤700的数据范围，代码简洁、结果准确。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=7e3+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;ll x[N],y[N];intmain(){ll n,ans,mx=0;cin>>n;for(ll i=1;i<=n;i++)cin>>x[i]>>y[i];for(ll i=1;i<n;i++)for(ll j=i+1;j<=n;j++){ans=2;for(ll k=1;k<=n;k++){if(k==i||k==j)continue;if((x[k]-x[i])*(y[k]-y[j])==(y[k]-y[i])*(x[k]-x[j]))ans++;}mx=max(mx,ans);}cout<<mx<<endl;return0;}