QBPOINT – SPOJ

Đề bài: http://vn.spoj.com/problems/QBPOINT/

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector <double> ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<<res/6;
    return 0;
}