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).