ematematikas.lt_2017_11_11

#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);
    }
}