Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- long long n;
- long long pocz = 0;
- long long konc = 0; ///ROZNICA MIEDZY POCZATKIEM A KONCEM MOZE BYC MAXYMALNIE N-1 (NIE MOZNA 2 RAZY WZIAC TEGO SAMEGO WEKTORA)
- long long akt_x = 0;
- long long akt_y = 0;
- long long wynik;
- long long max_wynik = 0;
- double dlug_pocz;
- double dlug_wyni;
- double dlug_konc;
- double cos_pocz_wyn;
- double cos_wyn_konc;
- long long pole;
- vector<pair<long long, long long> >vec;
- short sektor_a;
- short sektor_b;
- short przypisz_sektor(long long x, long long y)
- {
- if(x==0 && y>0)
- return 1;
- if(x>0 && y>0)
- return 2;
- if(x>0 && y==0)
- return 3;
- if(x>0 && y<0)
- return 4;
- if(x==0 && y<0)
- return 5;
- if(x<0 && y<0)
- return 6;
- if(x<0 && y==0)
- return 7;
- if(x<0 && y>0)
- return 8;
- }
- long long pole_skierowane(pair<long long, long long> A, pair<long long, long long> B)
- {
- return A.first*B.second - A.second*B.first;
- }
- bool comp(pair<long long, long long> left, pair<long long, long long> right) ///x,y
- {
- ///TE PONIZSZE 4 LINIJKI SA NIBY OK, ALE NIE SA OK. NIE WIEM CZEMU. PO PROSTU NIE SĄ (na dużych testach na gen.
- ///pokazuja segfaulta, na innych nie, a niezbyt chciało mi się bawić w ręczne sprawdzanie co jest nie talna testach gdzie n=200k).
- ///A bez tych 4 linijek to sortowanie nawet na malych nie dziala, w 74 i 76 tam zmienilem > na >= co w kilku przypadkach pomaga, ale nie rozwiazuje problemu
- /* if(left.first == 0 && left.second > 0) return 1;
- if(right.first == 0 && right.second > 0) return 0;
- if(left.first == 0 && right.first > 0) return 0; ///automatycznie left.second < 0
- if(right.first == 0 && left.first > 0) return 1;*/
- /*cout<<endl;
- cout<<"left.x: "<<left.first<<" left.y: "<<left.second<<endl;
- cout<<"right.x: "<<right.first<<" right.y: "<<right.second<<endl;
- if(left.first < 0 && right.first >= 0) {//cout<<"NA BAZIE 1 RETURN 0"<<endl;
- return false;}
- if(left.first >= 0 && right.first < 0) {//cout<<"NA BAZIE 2 RETURN 1"<<endl;
- return true;}
- // cout<<"NA BAZIE 3 RETURN "<<bool(pole_skierowane(left, right) < 0)<<endl;
- return pole_skierowane(left, right) < 0;*/
- ///SPROBUJEMY PODEJSCIA ALTERNATYWNEGO => PODZIAL NA 8 STREF, ĆWIARTKI UKLADU, I GRANICE CWIARTEK
- ///NIGDY NIE MAMY DO CZYNIENIA Z WEKTOREM (0,0) - takie odrzucilem przy wprowadzaniu danych
- sektor_a = przypisz_sektor(left.first, left.second);
- sektor_b = przypisz_sektor(right.first, right.second);
- if(sektor_a != sektor_b)
- return sektor_a < sektor_b;
- return pole_skierowane(left, right) < 0;
- }
- void add_to_sum(long long ind)
- {
- akt_x += vec[ind].first;
- akt_y += vec[ind].second;
- }
- void remove_from_sum(long long ind)
- {
- akt_x -= vec[ind].first;
- akt_y -= vec[ind].second;
- }
- void calc_wynik()
- {
- wynik = pow(akt_x, 2) + pow(akt_y, 2);
- }
- void calc_max_wynik()
- {
- max_wynik = max(max_wynik, wynik);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- long long tmp1;
- long long tmp2;
- ///WPROWADZENIE DANYCH
- cin>>n;
- for(long long i=0; i<n; i++)
- {
- cin>>tmp1;
- cin>>tmp2;
- if(tmp1 || tmp2)
- vec.push_back(make_pair(tmp1, tmp2));
- else
- {n--; i--;}
- }
- if(n==0)
- {cout<<0; return 0;}
- ///SORTOWANIE KATOWE
- sort(vec.begin(), vec.end(), comp);
- ///BEZ TEGO POJAWIAL SIE CZASEM PROBLEM DLA DANYCH, GDZIE BYLY 2/więcej WEKTORY W TYM SAMYM KIERUNKU,
- ///KONKRETNIE JAK PRZYCHODZILO DO TEGO ZE GASIENNICA PRZECHODZILA 2 RAZ NA POCZATEK, DLA NIEKTORYCH DANYCH WYSZŁY BŁĘDY
- vector <pair<long long, long long> > temp;
- temp.push_back(vec[0]);
- long long a_x;
- long long a_y;
- long long b_x;
- long long b_y;
- ///VEKTORY MAJA TAKI SAM KIERUNEK GDY: a_x/a_y = b_x/b_y => dla a_y=/=0 && b_y =/= 0 => a_x*b_y = b_x*a_y
- ///DLA a_y = 0 oraz b_y = 0, gdy a_x oraz b_x maja takie same znaki
- for(long long i=1; i<vec.size(); i++)
- {
- a_x = vec[i].first;
- a_y = vec[i].second;
- b_x = temp[temp.size()-1].first;
- b_y = temp[temp.size()-1].second;
- // cout<<"a_x: "<<a_x<<" a_y: "<<a_y<<" b_x: "<<b_x<<" b_y: "<<b_y<<endl;
- ///MUSIALEM UZYC ATAN2, CHOCIAZ CHCIALEM SIE BEZ NIEGO OBEJSC JAK W KOMENTARZU NIZEJ (175, 198)
- ///ALE a)TO JEST ZA WOLNE, b - ważniejsze)NIE DZIAŁA
- ///STWIERDZILEM ZE AKURAT TU, W PRZECIWIENSTWIE O TO CO CIE PYTALEM UZYCIE ATAN2 JEST SPOKO,
- ///BO NIE MUSIMY MARTWIC SIE O DOKLADNOSC, BO MA WYKRYC TYLKO I WYLACZNIE ROWNE KATY,
- ///NIC NIE DODAJEMY ITP, NA ZADNYM TESCIE Z GENERATORKI NIE BYLO Z TYM ZADNEGO PROBLEMU
- /*if(a_y && b_y)
- {
- if(a_x*b_y == b_x*a_y)
- {
- temp[temp.size()-1].first += a_x;
- temp[temp.size()-1].second += a_y;
- }
- else
- temp.push_back(vec[i]);
- }
- else if(!a_y && !b_y)///vec[i].second=0 oraz temp[i-1].second=0
- {
- if((a_x > 0 && b_x > 0)
- || (a_x < 0 && b_x < 0) )
- {
- temp[temp.size()-1].first += a_x;
- temp[temp.size()-1].second += a_y;
- }
- else
- temp.push_back(vec[i]);
- }
- else
- temp.push_back(vec[i]);*/
- if(atan2(a_x, a_y) == atan2(b_x, b_y))
- {
- temp[temp.size()-1].first += a_x;
- temp[temp.size()-1].second += a_y;
- }
- else
- temp.push_back(vec[i]);
- }
- vec = temp;
- n = vec.size();
- ///"ZDWOJENIE" VECTORA
- for(long long i=0; i<n; i++)
- vec.push_back(vec[i]);
- // for(long long i=0; i<2*n; i++)
- // cout<<"i: "<<i<<" x: "<<vec[i].first<<" y: "<<vec[i].second<<endl;
- pocz = 0;
- konc = 0;
- akt_x = vec[pocz].first;
- akt_y = vec[pocz].second;
- calc_wynik();
- calc_max_wynik();
- vec.push_back(make_pair(0,0));
- vec.push_back(make_pair(0,0));
- vec.push_back(make_pair(0,0));
- vec.push_back(make_pair(0,0)); ///DLA BEZPIECZENSTWA - JESLI ODWOLA SIE DO INDEKSU LEKKO POZA ZAKRESEM, TO NIC SIE NIE STANIE
- //return 0;
- while(konc <= 2*n)
- {
- ///ZWIEKSZ KONIEC
- // cout<<endl;
- //cout<<"ZWIEKSZAM KONIEC: "<<konc+1<<endl;
- konc++;
- add_to_sum(konc);
- if(pocz>n&& konc>n) ///CZASEM JEST W STANIE UCIAC CZAS O PRAWIE 50%
- {cout<<max_wynik; return 0;}
- if(konc-pocz>=n) ///JAK KOM. LINIJKA 9
- {
- // cout<<"USUWAM POCZ, NOWY: "<<pocz+1<<endl;
- remove_from_sum(pocz);
- pocz++;
- remove_from_sum(konc);
- konc--;
- calc_wynik();
- calc_max_wynik();
- }
- else{
- ///USUWAJ POCZATEK TAK DLUGO JAK TRZEBA
- while((pole_skierowane(vec[pocz], vec[konc]) > 0 && pocz!=konc)) ///POLE MOZE BYC ROWNE 0, ALE TYLKO W WYPADKU,
- {
- remove_from_sum(pocz);
- // cout<<"USUWAM POCZATEK, NOWY:"<<pocz+1<<endl;
- pocz++;
- remove_from_sum(konc);
- konc--;
- calc_wynik();
- calc_max_wynik();
- //cout<<"WYNIK: "<<wynik<<endl;
- }
- // cout<<"akt_x: "<<akt_x<<" akt_y: "<<akt_y<<endl;
- calc_wynik();
- calc_max_wynik();
- }
- }
- cout<<max_wynik;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement