URI Online Judge | 1137
Pontos Cocirculares
por Pablo Ariel Heiber 
Argentina
Timelimit: 6 Argentina
Você provavelmente sabe o que é um conjunto de pontos colineares: é um conjunto de pontos tal que existe uma linha reta que passa através de todos os pontos. Um conjunto de pontos cocirculares é definido da mesma forma, mas ao invés de uma linha reta, nós queremos saber se existe um círculo tal que todos os pontos do conjunto encontram-se sobre seu perímetro.
A International Collinear Points Center (ICPC) designou a você a seguinte tarefa: dado um conjunto de pontos, calcule o tamanho do maior subconjunto de pontos cocirculares.
Entrada
Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando o número de pontos no conjunto (1 ≤ N ≤ 100). Cada uma das próximas N linhas contém dois inteiros X e Y representando as coordenadas de um ponto do conjunto (-104 ≤ X,Y ≤ 104). Em cada caso de teste, não haverá dois pontos com mesma localização.
O último caso de teste é seguido por uma linha contendo apenas um zero.
Saída
Para cada caso de teste, imprima uma única linha com um único inteiro representando o número de pontos em um dos maiores subconjuntos da entrada que são cocirculares.
#include <iostream>
#include <algorithm>
#define MAXN 201
using namespace std;
typedef long long ll;
ll X[MAXN],Y[MAXN],squared[MAXN],resp,n,sqy[MAXN][MAXN],sqx[MAXN][MAXN],xy[MAXN][MAXN];
void addCircle(ll A,ll B,ll C){
ll cof1 = X[A]*(Y[B] - Y[C]) - Y[A]*(X[B] - X[C]) + xy[B][C];
if(cof1 == 0) return;
ll cof2 = squared[A]*(Y[B] - Y[C]) - Y[A]*(squared[B] - squared[C]) + sqy[B][C];
ll cof3 = squared[A]*(X[B] - X[C]) - X[A]*(squared[B] - squared[C]) + sqx[B][C];
ll cof4 = squared[A]*(xy[B][C]) - X[A]*(sqy[B][C]) + Y[A]*(sqx[B][C]);
ll temp = 0;
for(ll i=1;i<=n;i++){
ll val = cof1*squared[i] - cof2*X[i] + cof3*Y[i] - cof4;
if(val == 0) temp++;
}
resp = max(temp,resp);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while(cin >> n && n){
resp = min(n,2LL);
for(ll i=1;i<=n;i++){
cin >> X[i] >> Y[i];
squared[i] = X[i]*X[i] + Y[i]*Y[i];
}
for(ll i = 1; i <= n-1;i++){
for(ll j = i+1;j<=n;j++){
xy[i][j] = X[i]*Y[j] - X[j]*Y[i];
sqx[i][j] = squared[i]*X[j] - squared[j]*X[i];
sqy[i][j] = squared[i]*Y[j] - squared[j]*Y[i];
}
}
for(ll i=1;i<=n-2;i++){
for(ll j=i+1;j<=n-1;j++){
for(ll k=j+1;k<=n;k++){
addCircle(i,j,k);
}
}
}
cout << resp << '\n';
}
return 0;
}
0 Comentários