Cod sursa(job #1515660)

Utilizator dumitrubogdanDumitru Bogdan Mihai dumitrubogdan Data 1 noiembrie 2015 23:36:24
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 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;
};

void citire();
double getAngle(Point a, Point b);
bool seIntersecteaza(int a, int b);
void quickSort(double arr[], int left, int right);

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

    citire();
//    for(int i=0; i<n; i++){
//        printf("%.02f  %.02f\n",start[i], stop[i]);
//    }
//    printf("\n\n");
    quickSort(start,0,n-1);


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

    FILE * f = fopen("rays.out","w");
    if(n < 1)
        cnt = 0;
    fprintf(f,"%d",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;
}


void quickSort(double arr[], int left, int right) {
      int i = left, j = right;
      double tmp;
      double pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;

                  tmp = stop[i];
                  stop[i] = stop[j];
                  stop[j] = tmp;

                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}