#include #include #include typedef struct { int kdo; float kam; } kdokam; typedef struct { float Sx, Sy; float r; } kruznice; kruznice opis(float A[], float B[], float C[]); int comp(const void *a, const void *b); const float eps = 0.0001f; int main() { int N; scanf("%d", &N); float By[N][2]; for (int i = 0; i < N; i++) scanf("%f %f", &By[i][0], &By[i][1]); // V těchto proměnných si budeme pamatovat // doposavaď nejúspěšnější kružnici. int maxA = 0, maxB = 1, maxC = 2, maxN = 0; // Teď: Pro každou dvojici bodů... for (int A = 0; A < N; A++) for (int B = 0; B < N; B++) { if (A == B) continue; kdokam Cy[N-2]; int i = 0; int pozorujicich = N-2; // pro každý pozorující bod... for (int C = 0; C < N; C++) { if (C == A || C == B) continue; // zjisti, pod jakým úhlem úsečku AB pozoruje, // tedy jaký je úhel, který svírají vektory CA a CB. float CA[2], CB[2], BA[2]; CA[0] = By[A][0]-By[C][0]; CA[1] = By[A][1]-By[C][1]; CB[0] = By[B][0]-By[C][0]; CB[1] = By[B][1]-By[C][1]; BA[0] = By[A][0]-By[B][0]; BA[1] = By[A][1]-By[B][1]; float cosalfa = (CA[0]*CB[0]+CA[1]*CB[1]) / sqrt(CA[0]*CA[0]+CA[1]*CA[1]) / sqrt(CB[0]*CB[0]+CB[1]*CB[1]); if (cosalfa > 1 - eps || cosalfa < -1 + eps) { // C je na jedné přímce s A a B. pozorujicich--; continue; } if (BA[0]*CA[1]-BA[1]*CA[0] > eps) // Pokud se B nachází v jedné polorovině určené přímkou AB, cosalfa += 2.0; // zahešuj/zatřiď úplně jinam. // (Předpis hned vypadne z vektorového součinu.) Cy[i].kdo = C; Cy[i++].kam = cosalfa; } qsort(Cy, pozorujicich, sizeof(kdokam), &comp); int nasobnost; for (int i = 0; i < pozorujicich; i++) { if (i > 0 && Cy[i].kam - Cy[i-1].kam < eps) nasobnost++; else nasobnost = 1; if (nasobnost > maxN) { maxN = nasobnost; maxA = A; maxB = B; maxC = Cy[i].kdo; } } } if (maxN == 0) { printf("V zadáni není kružnice.\n"); return; } kruznice reseni = opis(By[maxA], By[maxB], By[maxC]); printf("S=(%f , %f), r=%f [%d bodu]\n", reseni.Sx, reseni.Sy, reseni.r, maxN + 2); } kruznice opis(float A[], float B[], float C[]) { kruznice opsana; // Kde následující popis vzít? Dá se spočítat i najít v tabulkách. float p = 2*(A[0]*(B[1]-C[1])+B[0]*(C[1]-A[1])+C[0]*(A[1]-B[1])); opsana.Sx = ((A[1]*A[1]+A[0]*A[0])*(B[1]-C[1]) +(B[1]*B[1]+B[0]*B[0])*(C[1]-A[1]) +(C[1]*C[1]+C[0]*C[0])*(A[1]-B[1]))/p; opsana.Sy = ((A[1]*A[1]+A[0]*A[0])*(C[0]-B[0]) +(B[1]*B[1]+B[0]*B[0])*(A[0]-C[0]) +(C[1]*C[1]+C[0]*C[0])*(B[0]-A[0]))/p; opsana.r = sqrt((A[0]-opsana.Sx)*(A[0]-opsana.Sx) +(A[1]-opsana.Sy)*(A[1]-opsana.Sy)); return opsana; } int comp(const void *a, const void *b) { const kdokam *C1 = (const kdokam *)a; const kdokam *C2 = (const kdokam *)b; return (C1->kam - C2->kam) > 0 ? 1 : -1; }