[tex](x_{0},y_{0})[/tex] ir [tex](x_{1},y_{1})[/tex], bei [tex]s_{0}[/tex] ir [tex]s_{1}[/tex] - atitinkamai primo ir antro apskritimų centrų koordinatės bei spindulių ilgiai, d - astumas tarp apskritimų centrų.
Nesunku pastebėti, kad klaidingi atvejai bus tada ir tik tada, kai
[tex]\begin{cases} d > s_{1}+s_{0} \text{ (išvis nekerta)}\\ d < |s_{1}-s_{0}| \text{ (vienas apskritimas kitame)} \\ d = 0, s_{1}=s_{0} \text{ (tie patys apskritimai)}\\\end{cases}[/tex],
o mus tenkins tik
[tex]\begin{cases} d < s_{1}+s_{0} \text{ (kirs apskritimą du kartus)}\\ d = s_{0}+s_{1} \text{ (apskritimai liesis)}\\\end{cases}[/tex]
C kodas: (dėl patogumo įdėjau ir čia: https://pastebin.com/XHiHYRGw)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//---------------------------------------------------------------------------------
#define MAX 100
#define FILE_NAME "input.txt"
//---------------------------------------------------------------------------------
// Funkciju prototipai
void duomenuNuskaitymas(int *sk, double x[], double y[], double s[]);
double distanceBetweenTwoPoints(int x0, int y0, int x1, int y1);
int searchForIntersects(int sk, double x[], double y[], double s[]);
int theMostIntersects(int arr[], int n);
//---------------------------------------------------------------------------------
int main()
{
int sk; // apskritimu skaicius
double x[MAX], y[MAX], s[MAX]; // apskritimu parametrai
duomenuNuskaitymas(&sk, x, y, s);
printf("Daugiausiai kartu kerta %d-asis apskritimas\n", searchForIntersects(sk, x, y, s)+1);
return 0;
}
//---------------------------------------------------------------------------------
// grazinamas indeksas apskritimo, kuris kertasi daugiasiai kartu
int theMostIntersects(int arr[], int n)
{
int index = 0, max = 0;
for(int i = 0; i<n; i++)
if(arr[i] > max){
max = arr[i];
index = i;
}
return index;
}
//---------------------------------------------------------------------------------
// Blogi atvejai:
// d > s1 + s0 (isvis nekerta)
// d < |s1 - s0| (vienas apskritimas kitame)
// d = 0 ir s1 = s0 (tie patys apskritimai)
//
// Geri atvejai:
// d < s1 + s0 (apskritimai kertami du kartus)
// d = s1 + s0 (apskritimai lieciasi)
//
// funkcija grazins to apskritimo, kuris daugiausiai kerta kitu, indeksa.
// Jeigu yra keli tokie apskritimai, bus grazinamas pirmiau duomenu faile
// pateikto apskritimo indeksas
int searchForIntersects(int sk, double x[], double y[], double s[])
{
int howManyIntersects[sk]; // kiek kiekvienas apskritimas kerta kitu
double d; // atstumas tarp dvieju tasku
// apnulinamos reiksmes kad galetume sumuoti susikirtimus:
for(int i = 0; i<sk; i++)
howManyIntersects[i] = 0;
for(int i = 0; i<sk; i++){ // einame per pradini apskritima
for(int j = 0; j<sk; j++){ // i-tasis apskritimas lyginamas su j-tuoju apskritimu
if(i != j){ // praleidziame vienodus apskritimus
d = distanceBetweenTwoPoints(x[i], y[i], x[j], y[j]);
if(d > s[i] + s[j] || d < fabs(s[i] - s[j]) || (d == 0 && s[i] == s[j]))
; // do nothing as those cases are wrong
else if(d < s[i] + s[j] || d == s[i] + s[j])
howManyIntersects[i]++; // vadinasi i-tasis apskritimas kerta j-taji apskritima
}
}
}
return theMostIntersects(howManyIntersects, sk);
}
//---------------------------------------------------------------------------------
// funkcija randa ir grazina atstuma tarp dvieju tasku
double distanceBetweenTwoPoints(int x0, int y0, int x1, int y1)
{
return sqrt(pow((x1-x0),2)+pow((y1-y0),2));
}
//---------------------------------------------------------------------------------
void duomenuNuskaitymas(int *sk, double x[], double y[], double s[])
{
FILE *fp = fopen(FILE_NAME, "r");
if(fp != NULL){
fscanf(fp, "%d", &*sk);
if(*sk > 0){
for(int i = 0; i<*sk; i++)
fscanf(fp, "%lf%lf%lf", &x[i], &y[i], &s[i]);
}else{
printf("Nekorektiska ivestis..\n");
exit(EXIT_FAILURE);
}
fclose(fp);
}else{
printf("Toks failas pavadinimu %s nerastas\n", FILE_NAME);
exit(EXIT_FAILURE);
}
}
