1322: 同心共筑中国梦
题目描述
平面上有N个坐标各异的点，现在PIPI想知道这N个点当中有多少组非共线的三个点，这三个点的外心也在这个N点之中？
PS：三个非共线的点可以确定一个三角形，三角形的外接圆的圆心就是这三个点的外心。
输入
第一行有一个正整数 n 代表平面上的点数。
接下来有 n 行，当中的第 i 行包含两个整数 x,y,代表第 i 个点的坐标。
- 1≤n≤2000
- -1e9<=x,y<=1e9
输出
输出一个整数代表答案。
样例输入
5
0 0
-2 0
0 2
-1 1
2 0
样例输出
2
思路
如果枚举所有的点则时间复杂度为 o（n^3logn），logn 为判断此时外心是否在点集内所需的时间，显然会超时。注意到外心即三角形外接圆的圆心且此题中没有具有相同坐标的点，所以枚举每一个点作为可能的外心，计算其它点到该点的距离，若有三个及以上的点拥有相同距离则根据组和数可知这些点可以构成 (cnt) * (cnt - 1) * (cnt - 2) / 6 个三角形，且三角形外心为当前所枚举的点。
#include<bits/stdc++.h>
using namespace std;
long long int x[2022], y[2022];
int main()
{
int n;scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%lld%lld", &x[i], &y[i]);long long int ans = 0;for(int i = 0; i < n; i++){
long long int dis[2022] = {
0};for(int j = 0; j < n; j++){
if(j != i){
dis[j] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); }}sort(dis, dis + n);for(int j = 1; j < n - 1; j++){
long long int cnt = 1;while(dis[j] == dis[j + 1]){
j++;cnt++;}if(cnt >= 3) {
ans += (cnt) * (cnt - 1) * (cnt - 2) / 6;} }}printf("%lld\n", ans);return 0;
}