fbpx

Problema #931 – SortareUnghi – Rezolvari PBInfo

de Mihai-Alexandru

Cerința

Se dau puncte distincte în plan. Asociem fiecărui punct semidreapta care pornește din originea sistemului de coordonate și trece prin acel punct. Să se afișeze punctele în ordine crescătoare a unghiului pe care semidreapta asociată îl face cu semidreapta spre plus infinit a axei OX. Dacă două unghiuri sunt egale se va afișa punctul cel mai apropiat de origine.

Date de intrare

Fișierul de intrare sortareunghi.in conține pe prima linie n, reprezentând numărul de puncte. Pe următoarele n linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct.

Date de ieșire

Fișierul de ieșire sortareunghi.out va conține n linii cu câte două numere separate prin câte un spațiu, reprezentând abscisa respectiv ordonata câte unui punct, în ordinea cerută.

Restricții și precizări

  • 1 ≤ n ≤ 100
  • Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001.
  • Unghiurile sunt în intervalul [0,360).

    Exemplu

    sortareunghi.in

    3
    1 1 
    -1 -1 
    -1 1

    sortareunghi.out

    1 1
    -1 1
    -1 -1
    #include <bits/stdc++.h>
    
    using namespace std;
    
    ifstream cin("sortareunghi.in");
    ofstream cout("sortareunghi.out");
    struct elem
    {
        int x , y;
    } ;
    
    int dist(elem a)
    {
        return a.x * a.x + a.y * a.y;
    }
    
    void citire(elem a[] , int &n)
    {
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
            cin >> a[i].x >> a[i].y;
    }
    
    void afisare(elem a[] , int n)
    {
        for(int i = 1 ; i <= n ; i++)
            cout << a[i].x << ' ' << a[i].y << '\n';
    }
    
    double unghi(elem a)
    {
        if(a.x > 0 && a.y > 0) return 1.0 * a.y / a.x;
        if(a.x < 0 && a.y > 0) return 10000 + 1.0 * (-a.x) / a.y;
        if(a.x < 0 && a.y < 0) return 20000 + 1.0 * a.y / a.x;
        if(a.x > 0 && a.y < 0) return 30000 + 1.0 * a.x / (-a.y);
        if(a.x == 0) if(a.y > 0) return 10000;
                        else return 30000;
        else if(a.y == 0) if(a.x > 0) return 0;
        else return 20000;
    }
    
    int comp(elem a , elem b)
    {
        return unghi(a) < unghi(b) || (unghi(a) == unghi(b) && dist(a) < dist(b));
    }
    int main()
    {
        elem a[1001];
        int n;
        citire(a , n);
        sort(a + 1 , a + n + 1 , comp);
        afisare(a , n);
        return 0;
    }
    Comentarii

S-ar putea sa iti placa