pravokutni.cpp

Bài toán

Cho n điểm toạ độ nguyên trên mặt phẳng. Đếm xem có bao nhiêu tam giác vuông mà có ba đỉnh nằm trong tập các đỉnh đã cho.

Độ phức tap

O(n^2 logn)

#include <stdio.h>

#include <algorithm>

#include <map>

using namespace std;

#define long long long

typedef pair<long, long> llll;

#define X first

#define Y second

int n;

llll a[12309];

llll minimal(llll u){

//printf("minimal(%lld, %lld)\n", u.X, u.Y);

long GCD = __gcd(abs(u.X), abs(u.Y));

if (u<llll()) GCD = -GCD;

u.X /= GCD; u.Y /= GCD;

return u;

}

llll xxfu(llll A, llll B){

return minimal(llll(B.X-A.X, B.Y-A.Y));

}

llll fn(llll u){

return llll(-u.Y, u.X);

}

long with_origin(llll O){

int i; long answer=0;

map<llll, int> ma;

for (i=1; i<=n; i++)

if (a[i]!=O) ma[xxfu(a[i], O)]++;

for (i=1; i<=n; i++)

if (a[i]!=O) answer += ma[minimal(fn(xxfu(O, a[i])))];

return answer/2;

}

main(){

int i; long answer=0;

scanf("%d", &n);

for (i=1; i<=n; i++)

scanf("%lld%lld", &a[i].X, &a[i].Y);

for (i=1; i<=n; i++)

answer += with_origin(a[i]);

printf("%lld\n", answer);

}

Nhận xét

Trong n điểm, cho một điểm làm góc vuông. Sắp xếp các điểm khác theo góc (đúng hơn là véc tơ tạo bởi tâm với các điểm còn lại).