C11TRCNT spoj – Bắn máy bay

Nguồn đề bài: http://vn.spoj.com/problems/C11TRCNT/

1. Đề bài C11TRCNT spoj

Vương quốc C11 sắp chuẩn bị gặp hiểm họa cực lớn từ vương quốc XYZ. Theo thông tin mật báo của điệp viên “Không Không Thấy”, rằng XYZ sẽ gửi một Đại đội máy bay B52 ra thả bom tại HN (thủ đô của C11), và quyết đem HN về thời kỳ đồ đá. Và thật may mắn, điệp viên của ta đã rất nhanh tay lấy được sơ đồ chiến thuật tấn công của địch.

Đại đội máy bay bao gồm tổng cộng N chiếc, được đánh số từ 1–>N. Mỗi chiếc sẽ có một vị trí xác định trong đội hình, và được cụ thể bằng một cặp số (x,y) cho biết tọa độ tương đối của nó. Theo nghiên cứu, cứ mỗi 3 chiếc trong đội hình tạo thành một hình tam giác sẽ tăng chỉ số chắc chắn của đội hình lên một đơn vị. Và độ an toàn của một chiếc máy bay trong đội hình là số lượng đội hình tam giác mà nó tham gia.

Vì thế ta cũng đã đề ra một chiến thuật, mỗi lần ta sẽ bắn rơi chiếc máy bay có độ an toàn nhỏ nhất trong đội hình của chúng.

Input

_ Dòng đầu tiên là số nguyên dương N (N<=200).

_ N dòng tiếp theo là các cặp số nguyên (x,y) cho biết tọa độ của các chiếc máy bay. (|x|,|y|<=1000000000)

Output

_ Cho biết chỉ số chắc chắn của đội hình lúc đầu và số thứ tự của chiếc máy bay được bắn rơi đầu tiên (nếu có nhiều máy bay cùng độ an toàn thì chọn chiếc có số thứ tự nhỏ nhất).

Example

Input:
4
1 2
0 0
1 0
2 0

Output:
3 2

2. Code tham khảo C11TRCNT spoj

Gợi ý: bạn à, cứ trâu mà làm nha! 3 for

#include <bits/stdc++.h>
#define fs first
#define sc second
#define oo 1e9
#define LL long long
using namespace std;
typedef pair<int,int> II;
    int n,f[205],tong=0,ds2=oo,id=0;
    II a[205];
II operator-(II a,II b){return II(a.fs-b.fs,a.sc-b.sc);}
LL operator*(II a,II b){return (LL)a.fs*b.sc-(LL)a.sc*b.fs;}
bool ok(int i,int j,int k)
{
    II ij=a[j]-a[i];
    II ik=a[k]-a[i];
    if(ij*ik==0) return 0;
    return 1;
}
int main()
{
    //freopen("a.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i].fs>>a[i].sc;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
            for(int k=j+1; k<=n; k++)
            {
                if(ok(i,j,k))
                    tong++;
            }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        if(j!=i)
        {
            for(int k=1; k<=n; k++)
                if(k!=j&&k!=i)
                {
                    if(ok(i,j,k))
                        f[i]++;
                }
        }
        f[i]/=2;
        if(f[i]<ds2) {ds2=f[i]; id=i;}
        if(f[i]==ds2&&id>i) id=i;
    }
    cout<<tong<<" "<<id;
}