题解：奶牛共线问题

一、问题分析

本题要求找出牧场中所有三头共线的奶牛集合，并按规则排序输出。核心在于高效判断三点共线，同时避免浮点运算带来的精度问题。

二、关键思路

1. 共线判断原理
   三点$(x_1,y_1)$、$(x_2,y_2)$、$(x_3,y_3)$共线的充要条件是向量$\overrightarrow{(x_1,y_1)(x_2,y_2)}$与$\overrightarrow{(x_2,y_2)(x_3,y_3)}$的叉积为0，即：

   $$(x_2 - x_1)(y_3 - y_2) - (y_2 - y_1)(x_3 - x_2) = 0 $$

   通过整数运算避免浮点误差。

2. 枚举优化

   • 三重循环枚举：直接枚举所有三元组$(i,j,k)$（保证$i<j<k$），利用叉积判断共线。此方法时间复杂度为$O(N^3)$，适用于$N\leq770$的规模（运算量约$770^3\approx4.5\times10^8$，需优化常数项）。
   • 斜率分组优化：对每个点$i$，统计其他点与$i$的斜率（用最简分数表示），同斜率的点属于同一共线组。若某组有$m$个点，则贡献$\binom{m}{2}$个三元组（包含点$i$）。此方法时间复杂度为$O(N^2)$，更高效。

3. 结果排序
   枚举时按$i<j<k$顺序确保每组内ID升序，整体枚举顺序天然满足字典序要求，无需额外排序。

三、代码实现

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<deque>
#include<functional>
#include<iterator>
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<sstream>
#define CPY(A, B) memcpy(A, B, sizeof(A))
typedef long long LL;
typedef unsigned long long uLL;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const double OO = 1e20;
const double PI = acos (-1.0);
int dx[]= {0,1,1,1,0,-1,-1,-1};
int dy[]= {1,1,0,-1,-1,-1,0,1};
int gcd (const LL &a, const LL &b) {return b==0?a:gcd (b,a%b);}
using namespace std;
struct NN {
    int x,y;
} nn[780];
NN dis[780][780];
vector<int> ANS;
int main() {
    int n; cin>>n;
    for (int i=0; i<n; ++i) {cin>>nn[i].x>>nn[i].y;}
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            dis[i][j].x=nn[i].x-nn[j].x;
            dis[i][j].y=nn[i].y-nn[j].y;
        }//计算距离
    }
    for (int i=0; i<n-2; ++i) {
        for (int j=i+1; j<n-1; ++j) {
            for (int k=j+1; k<n; ++k) {
                if (dis[i][j].x*dis[j][k].y==dis[j][k].x*dis[i][j].y) {
                    ANS.push_back (i);
                    ANS.push_back (j);
                    ANS.push_back (k);
                }//存储答案
            }
        }
    }
    cout<<ANS.size() /3<<endl; int cas=1;
    if (!ANS.empty() ) {
        vector<int>::iterator it;
        for (it=ANS.begin(); it!=ANS.end(); ++it) {
            (cas%3) ? cout<<*it+1<<" ":cout<<*it+1<<endl;
            cas++;
        }
    }
    return 0;
}