TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

torta.cpp    712 b      izvorni kod rešenja
torta.tests.rar    481,081 b      test primeri

zadatak: Torta

Mlađani Zi će uskoro da diplomira. Njegovi drugari su odlučili da mu za poklon naprave beskonačnu veliku tortu. Nakon što su tortu ispekli, nafilovali i ukrasili, drugari su odlučili da tortu iseku u automatskom sekaču. Automatski sekač je naprava koju su Zijevi drugari, elektroničari napravili tokom studija. Sekač radi na sledećem principu: torta se ubaci u sekač, zatim se unese željeni broj rezova n. Sekač će zatim iseći tortu tačno n puta. Ukoliko posmatramo tortu kao beskonačnu pravu, svaki rez predstavlja pravu u toj ravni.

Automatski sekač će odabrati položaj n rezova nasumično, i nakon završenog sečenja će odštampati izveštaj o položaju svakog od n rezova. Sekač je isprogramiran tako da se nikad neće desiti da tri različita reza prolaze kroz istu tačku na torti. U izveštaju sekača svaki rez je opisan dvema tačkama u ravni torte kroz koje prolazi dati rez.

Nakon što su isekli tortu, Zijevi drugari su gledali sekačev izveštaj ne bi li utvrdili na koliko parčića je torta isečena. Obično je mlađani Zi taj koji bi pomogao drugarima u rešavanju sličnih problema. Pošto je torta iznenađenje, drugari su odlučili da vas priupitaju za pomoć.

Pomozite Zijevim drugarima da, koristeći izveštaj sekača odrede na koliko parčića je torta isečena.

Ulaz:

(Ulazni podaci se nalaze u datoteci torta.in) U prvom redu ulazne datoteke nalazi se prirodan broj n (1 ≤ n ≤ 106), koji predstavlja broj rezova koje je sekač napravio. U svakom od narednih n redova nalaze se četiri cela broja x1, y1, x2, y2 razdvojenih razmakom, koji predstavljaju koordinate dveju tačaka kroz koje dati rez prolazi. Ukoliko tortu zamislimo kao beskonačnu ravan, dati rez predstavlja pravu koja prolazi kroz tačke (x1, y1) i (x2, y2). Svaka od koordinata je u opsegu od -10 do 109. Nikoja tri reza neće prolaziti kroz istu tačku na torti.

Izlaz:

(Izlazne podatke upisati u datoteku torta.out) U prvi red izlazne datoteke treba upisati prirodan broj k, koji predstavlja broj parčića na koje je torta isečena po modulu 1.000.003.

Primer 1:

torta.in      torta.out
4
0 0 0 1
1 0 1 1
2 0 2 1
3 0 3 1
        
5

Primer 2:

torta.in      torta.out
3
0 0 1 2
1 2 2 0
0 0 2 0
        
7

Primer 3:

torta.in      torta.out
3
0 0 0 1
1 0 1 1
0 0 1 0
        
6
fajl: torta.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

int main() {

  ifstream fin("torta.in");
  ofstream fout("torta.out");

  int n; fin >> n;
  vector<double> angle;
  for (int i=0; i<n; ++i) {
    double x1, y1, x2, y2;
    fin >> x1 >> y1 >> x2 >> y2;
    angle.push_back(atan2(x1-x2, y1-y2));
  }
  
  sort(angle.begin(), angle.end());
  long long tot = 1, curr = 1;
  long long longN=n;
  tot+= longN*(longN+1)/2;
  for (int i=1; i<n; ++i, ++curr)
    if (angle[i] - angle[i-1] > 1.0e-6) {
      tot-=curr*(curr-1)/2;
      curr = 0;
    } 
  tot-=curr*(curr-1)/2;
  tot %= 1000003;

  fout << tot << endl;

  fin.close(); fout.close();

}