Revenge of Collinearity

Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 612 Accepted Submission(s): 207

Problem Description

In
geometry, collinearity is a property of a set of points, specifically,
the property of lying on a single line. A set of points with this
property is said to be collinear (often misspelled as colinear).
---Wikipedia

Today,
Collinearity takes revenge on you. Given a set of N points in
two-dimensional coordinate system, you have to find how many set of
<P_i, P_j, P_k> from these N points are collinear. Note that <P_i, P_j, P_k> cannot contains same point, and <P_i, P_j, P_k> and <P_i, P_k, P_j> are considered as the same set, i.e. the order in the set doesn’t matter.

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case begins with an integer N, following N lines, each line contains two integers Xi and Yi, describing a point.

[Technical Specification]
1. 1 <= T <= 33
2. 3 <= N <= 1 000
3. -1 000 000 000 <= Xi, Yi <= 1 000 000 000, and no two points are identical.
4. The ratio of test cases with N > 100 is less than 25%.

Output

For each query, output the number of three points set which are collinear.

Sample Input

2
3
1 1
2 2
3 3
4
0 0
1 0
0 1
1 1

Sample Output

1
0

Source

BestCoder Round #10

题意:平面上有n个点,统计有多少个三个点在一条直线上（注意:(1,2,3)和(1,3,2)相同）。

题解:这题O（n^3）会炸。。所以想办法优化，然后就想到斜率。但是斜率不存在怎么办？？

1.然后看了别人的代码，求出 y1 - y2 与 x1 - x2 的最大公约数d，斜率可以直接用(（y1-y2)/d,(x1-x2)/d)进行唯一的表示。

2。对所有点进行排序，先按x坐标,然后再按y坐标排序。接着对于第 i 个点,我们找到 p (p>=2)个点与其共线,那么总共有p*(p-2)种可能的组合方法。

3.用pair 和 map 将条件 1，2联系起来。map进行计数,pair用来存斜率。

4.好巧妙的一个题。

pair是可以直接根据里面的元素进行判断是否相等的.

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

typedef pair<int,pair<int,int> > piii;

int main()

{

    pii a(,);

    pii b(,);

    printf("%d\n",a==b);

    piii c(,make_pair(,));

    piii d(,make_pair(,));

    printf("%d\n",c==d);

    return ;

}

/*1 1*/

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

using namespace std;

typedef long long LL;

const int N = ;

struct Point{

    int x,y;

}p[N];

int cmp(Point a,Point b){

    if(a.x==b.x) return a.y<b.y;

    return a.x<b.y;

}

int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

map<pair<int,int>,int> mp;

map<pair<int,int>,int>::iterator it;

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        int n;

        scanf("%d",&n);

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

            scanf("%d%d",&p[i].x,&p[i].y);

        }

        int ans = ;

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

            mp.clear();

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

                int x = p[j].x - p[i].x;

                int y = p[j].y - p[i].y;

                int d = gcd(x,y);

                x/=d,y/=d;

                mp[make_pair(x,y)]++;

            }

            for(it = mp.begin();it!=mp.end();it++){

                if(it->second>=){

                    int t = it->second;

                    ans+=t*(t-)/;

                }

            }

        }

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

    }

    return ;

}

巴特西

hdu 5020(斜率的表示+STL)

Revenge of Collinearity

最新文章

热门文章