POJ 3174 Alignment of the Planets (暴力求解)

题意：给定 n 个坐标，问你三个共线的有多少组。

析：这个题真是坑啊，写着 n <= 770，那么一秒时间，三个循环肯定超时啊，我一直不敢写了，换了好几种方法都WA了，也不知道为什么，在比赛时坑我了两个多小时，

最后看到那么多过的，就想试试，真的AC ，三个循环一点没优化，竟然才150多毫秒，。。。。POJ的数据真是水啊。

没什么好说的，只要三个循环，然后判断斜率就好了。

代码如下：

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <string>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const double eps = 1e-11;

const int maxn = 770 + 5;

struct Node{

    int id1, id2, id3;

    Node(int a, int b, int c) : id1(a), id2(b), id3(c) { }

    bool operator < (const Node &p) const{

        if(id1 != p.id1)  return id1 < p.id1;

        else if(id2 != p.id2)  return id2 < p.id2;

        else return id3 < p.id3;

    }

};

struct node{

    int id, x, y;

};

struct node1{

    int id;

    double rad;

    bool operator < (const node1 &p) const{

        return rad < p.rad || (p.rad == rad && id < p.id);

    }

};

double Fabs(double x){

    return x < 0.0 ? -x : x;

}

vector<Node> ans;

node a[maxn];

int main(){

    int n, x, y, c;

    scanf("%d", &n);

    for(int i = 0; i < n; ++i){

        scanf("%d %d", &x, &y);

        a[i].id = i+1;

        a[i].x = x+1;

        a[i].y = y+1;

    }

    for(int i = 0; i < n; ++i){

        for(int j = i+1; j < n; ++j){

            for(int k = j+1; k < n; ++k){

                if((a[i].y-a[j].y)*(a[i].x-a[k].x) == (a[i].y-a[k].y)*(a[i].x-a[j].x)){

                    ans.push_back(Node(a[i].id, a[j].id, a[k].id));

                }

            }

        }

    }

//    sort(ans.begin(), ans.end());

    printf("%d\n", ans.size());

    for(int i = 0; i < ans.size(); ++i)

        printf("%d %d %d\n", ans[i].id1, ans[i].id2, ans[i].id3);

    return 0;

}

/*

6

1 2

1 3

1 4

1 5

1 6

1 1

*/