Cod sursa(job #1515651)

Utilizator dumitrubogdanDumitru Bogdan Mihai dumitrubogdan Data 1 noiembrie 2015 22:58:17
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdbool.h>

using namespace std;
#define N 200000
#define PI 3.14159265359

double start[N], stop[N];
int n;

typedef struct Point {
    float x;
    float y;
};

double getAngle(Point a, Point b);
int sorting(double *array, int p, int r);
void quick_sort(double *array, int p, int r);
void citire();
bool seIntersecteaza(int a, int b);


int main ()
{
    int cnt = 0;
    int last = 0;

    citire();

    quick_sort(start,0,n-1);

    for(int i=1; i<n; i++){
        if( seIntersecteaza(i,last) == false ){
           // printf("%f %f  -  %f %f\n",start[last],stop[last],start[i],stop[i]);
            last = i;
            cnt++;
        }
    }

    FILE * f = fopen("rays.out","w");
    fprintf(f,"%d",cnt);
    //cout<<cnt;
    fclose(f);

    return 0;
}

void citire(){
    FILE * f = fopen("rays.in","r");
    fscanf(f,"%d",&n);

    for(int i=0;i<n;i++){
        int x, y1, y2;
        Point p1, p2, pRef;

        fscanf(f,"%d%d%d",&x,&y1,&y2);

        pRef.x = 1.0; pRef.y = 0.0;
        p1.x = x; p1.y = y1;
        p2.x = x; p2.y = y2;

        start[i] = getAngle(p1,pRef);
        stop[i] = getAngle(p2,pRef);

        if( fabs(start[i]-stop[i]) > 180 ){
            if( start[i] < stop[i] )
                swap(start[i] , stop[i]);
        }
        else{
            if( start[i] > stop[i])
                swap(start[i], stop[i]);
        }
    }
    fclose(f);
}


bool seIntersecteaza(int a, int b){
    if( start[a] <= stop[a] ){
            if( start[b] <= stop[b] ){
                if( start[a] > stop[b] ){
                    return false;
                }
            }
            else{
                if( start[a] > stop[b] && stop[a] < start[b]){
                    return false;
                }
            }
    }
        else{
            if( start[b] < stop[b] ){
                if( start[a] > stop[b] && stop[a] < start[b] ){
                    return false;
                }
            }
    }
    return true;
}

double getAngle(Point a, Point b){
    double angle = atan2(a.y, a.x) - atan2(b.y, b.x);
    angle = angle * 360 / (2*PI);
    if (angle < 0){
        angle = angle + 360;
    }
    return angle;
}

int sorting(double *stop, int p, int r){
    double x=stop[r];
    int i=p-1;
    int j;

    for( j=p; j<=r-1; j++ ){
        if( stop[j] <= x ){
            i++;
            swap(stop[i], stop[j]);
            swap(start[i], start[j]);
        }
    }
    swap(stop[i+1], stop[r]);
    swap(start[i+1], start[r]);
    return (i+1);
}

void quick_sort(double *stop, int p, int r)
{
    int q;
    if(p<r){
        q = sorting(stop,p,r);
        quick_sort(stop,p,q-1);
        quick_sort(stop,q+1,r);
    }
}