本文主要是介绍HLJUOJ1125(暴力三点一线)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
两点确定一条直线
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 19 Solved: 11
[ Submit][ Status][ Web Board]
Submit: 19 Solved: 11
[ Submit][ Status][ Web Board]
Description
给一个15000 * 15000 的区域, 坐标都是整数.
其中有N个点,N ＜＝ ７７０．问总共有多少个３点共线的组合．并按升序（点的ＩＤ）输出所有的组合．（先按第一个点的ＩＤ升序，然后第二个，然后第三个）
Input
多组测试数据，读到文件末尾
每组数据第一行一个数n
接下来n行，第i行两个数x,y，代表ID为i的点的坐标为x，y
所有输入均为整数
Output
每组样例第一行一个数k，代表三点共线的个数
接下来k行，每行三个数，代表共线的三个点的ID
Sample Input
16
39 16
31 6
9 8
28 12
39 17
21 27
46 30
20 26
36 20
29 28
47 28
20 13
21 32
36 3
19 12
33 28
Sample Output
4
2 5 11
4 7 9
7 8 16
10 11 16
解题思路：
根据数据，我们可以暴力枚举每三个不同的点，如果向量AB与向量AC的叉积等于0的话，说明ABC三点共线。
完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;struct node
{int x;int y;
}q[10001];int s[10000001];bool check(node a , node b , node c)
{return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) == 0 ? true : false;
}int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifint n;while(~scanf("%d",&n)){for(int i = 1 ; i <= n ; i ++){scanf("%d%d",&q[i].x , &q[i].y);}int t = 1;int 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 ++){if(check(q[i] , q[j] , q[k])){cnt++;s[t++] = i;s[t++] = j;s[t++] = k;}}}}printf("%d\n",cnt);/* for(int i = 1 ; i < t ; i ++)cout << s[i] << " " ;cout << endl;*/for(int i = 1 ; i < t ; i++){if(i % 3 == 0)printf(" %d\n",s[i]);else{if(i % 3 == 1)printf("%d",s[i]);elseprintf(" %d",s[i]);}}}
}
这篇关于HLJUOJ1125(暴力三点一线)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
