LGOJ P1142 轰炸 解题报告

题目链接

LGOJ P1142 轰炸

解题思路

一道比较简单的计算几何题
我们知道，两点确定一条直线。所以我们采取枚举两点的方法，以此来确定一条直线。然后，我们可以枚举其他点，判断它们是否在此直线上，统计答案。
但是，如何判断第三点是否在直线上呢？ 一般地，初中生会采取直线的斜截式方程$y=kx+b$y=kx+b，但是这其中，$k,b$k,b都可能出现浮点数误差。有什么好方法呢？
其实，我们可以采用直线的两点式方程$(x-x_1)(y-y_2)=(x-x_2)(y-y_1)$(x−x1​)(y−y2​)=(x−x2​)(y−y1​)
其中$(x_1,y_1)$(x1​,y1​)和$(x_2,y_2)$(x2​,y2​)为已知直线上的点。
ok，nice！
时间复杂度$O(n^3)$O(n3)（对于$n\leq700$n≤700的数据这也能过？惊了）

详细代码

#define USEFASTERREAD 1 

#define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]\n", __func__, __LINE__)
#define putline putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>

#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO {
	void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);} 
	template<typename T> inline IO r(T& x)const	{
	    x = 0; T f = 1; char ch = getchar();
	    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
	    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
	    x *= f; return *this;
	}
	template<typename T> inline IO w(T x)const {
	    if(x < 0) {putchar('-'); x = -x;}
	    if(x >= 10) w(x / 10);
	    putchar(x % 10 + '0'); return *this;
	}
	template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}
	template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}
	inline IO l() {putline; return *this;}
	inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x > 0 ? x : -x;} 

#include<algorithm>
using namespace std;
const int MAXN = 705;
int n;
struct Node {
	ll x, y;
	Node(ll x = 0, ll y = 0) : x(x), y(y) {}
	bool operator < (const Node& a)const {
		if(x != a.x) return x < a.x;
		return y < a.y;
	}
}A[MAXN];

bool sameline(Node a, Node a1, Node a2) {
	return (a.x - a1.x) * (a.y - a2.y) == (a.x - a2.x) * (a.y - a1.y);
}
int ans = 0;
int main() {
	io.r(n);
	Rep(i, 1, n) io.r(A[i].x).r(A[i].y);
	sort(A + 1, A + 1 + n);
	Rep(i, 1, n)
		Rep(j, i + 1, n) {
			int sum = 0;
			 Rep(k, 1, n) 
			 	if(i != k && j != k) {
					if(sameline(A[k], A[i], A[j])) sum++;
				}
			ans = Max(ans, sum + 2);//注意！
		}
	io.wl(ans);
	return 0;
}

P.S 洛谷的评测机越来越慢了