[LightOJ 1292] Laser Shot （几何，判断共线）

本文主要是介绍[LightOJ 1292] Laser Shot （几何，判断共线），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LightOJ - 1292
刚开始写的时候是O( $n^3log(n)$ )的，枚举两个点，得到一条直线，用set记录下来，然后再 O( $n$ )地计数，居然没有卡过 orz
听了学长的教导，get到一个几何常用思路，正确解法如下
枚举一个点，再枚举其他点，计算到这个点的斜率，make_pair(dx,dy)塞到map里，把相同斜率的计数一下
这样时间复杂度为 O( $n^2log(n)$ )

#if _WIN32||_WIN64
#define lld I64d
#define llu I64u
#endif
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}int N;
int inpt[710][2];map <pair<int,int>,int> Map;int main()
{int T;scanf("%d", &T);for(int ck=1; ck<=T; ck++){scanf("%d", &N);for(int i=1; i<=N; i++){scanf("%d%d", &inpt[i][0], &inpt[i][1]);}int ans=0;for(int i=1; i<=N; i++){Map.clear();for(int j=1; j<=N; j++){if(i==j) continue;int dx=inpt[i][0]-inpt[j][0],dy=inpt[i][1]-inpt[j][1];if(dx<0) {dx=-dx;dy=-dy;}int G=GCD(dx,dy);dx/=G;dy/=G;Map[make_pair(dx,dy)]++;ans=maxx(Map[make_pair(dx,dy)],ans);}}printf("Case %d: %d\n", ck, ans+1);}return 0;
}