Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. long long n;
  8. long long pocz = 0;
  9. long long konc = 0; ///ROZNICA MIEDZY POCZATKIEM A KONCEM MOZE BYC MAXYMALNIE N-1 (NIE MOZNA 2 RAZY WZIAC TEGO SAMEGO WEKTORA)
  10. long long akt_x = 0;
  11. long long akt_y = 0;
  12. long long wynik;
  13. long long max_wynik = 0;
  14.  
  15.  
  16. double dlug_pocz;
  17. double dlug_wyni;
  18. double dlug_konc;
  19.  
  20. double cos_pocz_wyn;
  21. double cos_wyn_konc;
  22.  
  23. long long pole;
  24.  
  25. vector<pair<long long, long long> >vec;
  26.  
  27.  
  28. short sektor_a;
  29. short sektor_b;
  30.  
  31. short przypisz_sektor(long long x, long long y)
  32. {
  33.     if(x==0 && y>0)
  34.         return 1;
  35.     if(x>0 && y>0)
  36.         return 2;
  37.     if(x>0 && y==0)
  38.         return 3;
  39.     if(x>0 && y<0)
  40.         return 4;
  41.     if(x==0 && y<0)
  42.         return 5;
  43.     if(x<0 && y<0)
  44.         return 6;
  45.     if(x<0 && y==0)
  46.         return 7;
  47.     if(x<0 && y>0)
  48.         return 8;
  49. }
  50.  
  51.  
  52. long long pole_skierowane(pair<long long, long long> A, pair<long long, long long> B)
  53. {
  54.     return A.first*B.second - A.second*B.first;
  55. }
  56. bool comp(pair<long long, long long> left, pair<long long, long long> right) ///x,y
  57. {
  58.     ///TE PONIZSZE 4 LINIJKI SA NIBY OK, ALE NIE SA OK. NIE WIEM CZEMU. PO PROSTU NIE SĄ (na dużych testach na gen.
  59.     ///pokazuja segfaulta, na innych nie, a niezbyt chciało mi się bawić w ręczne sprawdzanie co jest nie talna testach gdzie n=200k).
  60.     ///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
  61.  
  62.  /*   if(left.first == 0 && left.second > 0) return 1;
  63.     if(right.first == 0 && right.second > 0) return 0;
  64.  
  65.     if(left.first == 0 && right.first > 0) return 0; ///automatycznie left.second < 0
  66.     if(right.first == 0 && left.first > 0) return 1;*/
  67.  
  68.  
  69.  
  70.     /*cout<<endl;
  71.     cout<<"left.x: "<<left.first<<" left.y: "<<left.second<<endl;
  72.     cout<<"right.x: "<<right.first<<" right.y: "<<right.second<<endl;
  73.  
  74.     if(left.first < 0 && right.first >= 0) {//cout<<"NA BAZIE 1 RETURN 0"<<endl;
  75.     return false;}
  76.     if(left.first >= 0 && right.first < 0) {//cout<<"NA BAZIE 2 RETURN 1"<<endl;
  77.     return true;}
  78.  
  79.  
  80.   // cout<<"NA BAZIE 3 RETURN "<<bool(pole_skierowane(left, right) < 0)<<endl;
  81.     return pole_skierowane(left, right) < 0;*/
  82.  
  83.     ///SPROBUJEMY PODEJSCIA ALTERNATYWNEGO => PODZIAL NA 8 STREF, ĆWIARTKI UKLADU, I GRANICE CWIARTEK
  84.     ///NIGDY NIE MAMY DO CZYNIENIA Z WEKTOREM (0,0) - takie odrzucilem przy wprowadzaniu danych
  85.  
  86.     sektor_a = przypisz_sektor(left.first, left.second);
  87.     sektor_b = przypisz_sektor(right.first, right.second);
  88.  
  89.     if(sektor_a != sektor_b)
  90.         return sektor_a < sektor_b;
  91.  
  92.     return pole_skierowane(left, right) < 0;
  93.  
  94.  
  95.  
  96. }
  97. void add_to_sum(long long ind)
  98. {
  99.     akt_x += vec[ind].first;
  100.     akt_y += vec[ind].second;
  101. }
  102.  
  103. void remove_from_sum(long long ind)
  104. {
  105.     akt_x -= vec[ind].first;
  106.     akt_y -= vec[ind].second;
  107. }
  108.  
  109. void calc_wynik()
  110. {
  111.     wynik = pow(akt_x, 2) + pow(akt_y, 2);
  112. }
  113.  
  114. void calc_max_wynik()
  115. {
  116.     max_wynik = max(max_wynik, wynik);
  117. }
  118.  
  119.  
  120. int main()
  121. {
  122.     ios_base::sync_with_stdio(0);
  123.     cin.tie(0);
  124.  
  125.     long long tmp1;
  126.     long long tmp2;
  127.  
  128.     ///WPROWADZENIE DANYCH
  129.     cin>>n;
  130.  
  131.  
  132.     for(long long i=0; i<n; i++)
  133.     {
  134.         cin>>tmp1;
  135.         cin>>tmp2;
  136.  
  137.         if(tmp1 || tmp2)
  138.             vec.push_back(make_pair(tmp1, tmp2));
  139.         else
  140.             {n--; i--;}
  141.     }
  142.  
  143.     if(n==0)
  144.         {cout<<0; return 0;}
  145.  
  146.     ///SORTOWANIE KATOWE
  147.     sort(vec.begin(), vec.end(), comp);
  148.  
  149.     ///BEZ TEGO POJAWIAL SIE CZASEM PROBLEM DLA DANYCH, GDZIE BYLY 2/więcej WEKTORY W TYM SAMYM KIERUNKU,
  150.     ///KONKRETNIE JAK PRZYCHODZILO DO TEGO ZE GASIENNICA PRZECHODZILA 2 RAZ NA POCZATEK, DLA NIEKTORYCH DANYCH WYSZŁY BŁĘDY
  151.     vector <pair<long long, long long> > temp;
  152.     temp.push_back(vec[0]);
  153.  
  154.     long long a_x;
  155.     long long a_y;
  156.     long long b_x;
  157.     long long b_y;
  158.  
  159.     ///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
  160.     ///DLA a_y = 0 oraz b_y = 0, gdy a_x oraz b_x maja takie same znaki
  161.  
  162.  
  163.     for(long long i=1; i<vec.size(); i++)
  164.     {
  165.         a_x = vec[i].first;
  166.         a_y = vec[i].second;
  167.         b_x = temp[temp.size()-1].first;
  168.         b_y = temp[temp.size()-1].second;
  169.  
  170.        // cout<<"a_x: "<<a_x<<" a_y: "<<a_y<<" b_x: "<<b_x<<" b_y: "<<b_y<<endl;
  171.  
  172.         ///MUSIALEM UZYC ATAN2, CHOCIAZ CHCIALEM SIE BEZ NIEGO OBEJSC JAK W KOMENTARZU NIZEJ (175, 198)
  173.         ///ALE a)TO JEST ZA WOLNE, b - ważniejsze)NIE DZIAŁA
  174.  
  175.         ///STWIERDZILEM ZE AKURAT TU, W PRZECIWIENSTWIE O TO CO CIE PYTALEM UZYCIE ATAN2 JEST SPOKO,
  176.         ///BO NIE MUSIMY MARTWIC SIE O DOKLADNOSC, BO MA WYKRYC TYLKO I WYLACZNIE ROWNE KATY,
  177.         ///NIC NIE DODAJEMY ITP, NA ZADNYM TESCIE Z GENERATORKI NIE BYLO Z TYM ZADNEGO PROBLEMU
  178.         /*if(a_y && b_y)
  179.         {
  180.             if(a_x*b_y == b_x*a_y)
  181.             {
  182.                 temp[temp.size()-1].first += a_x;
  183.                 temp[temp.size()-1].second += a_y;
  184.             }
  185.  
  186.             else
  187.                 temp.push_back(vec[i]);
  188.         }
  189.         else if(!a_y && !b_y)///vec[i].second=0 oraz temp[i-1].second=0
  190.             {
  191.                 if((a_x > 0 && b_x > 0)
  192.                 || (a_x < 0 && b_x < 0) )
  193.                 {
  194.                     temp[temp.size()-1].first += a_x;
  195.                     temp[temp.size()-1].second += a_y;
  196.                 }
  197.                 else
  198.                     temp.push_back(vec[i]);
  199.             }
  200.         else
  201.             temp.push_back(vec[i]);*/
  202.  
  203.         if(atan2(a_x, a_y) == atan2(b_x, b_y))
  204.         {
  205.             temp[temp.size()-1].first += a_x;
  206.             temp[temp.size()-1].second += a_y;
  207.         }
  208.  
  209.         else
  210.             temp.push_back(vec[i]);
  211.  
  212.     }
  213.  
  214.     vec = temp;
  215.     n = vec.size();
  216.  
  217.  
  218.  
  219.     ///"ZDWOJENIE" VECTORA
  220.     for(long long i=0; i<n; i++)
  221.         vec.push_back(vec[i]);
  222.  
  223. //    for(long long i=0; i<2*n; i++)
  224.   //    cout<<"i: "<<i<<" x: "<<vec[i].first<<" y: "<<vec[i].second<<endl;
  225.  
  226.     pocz = 0;
  227.     konc = 0;
  228.  
  229.     akt_x = vec[pocz].first;
  230.     akt_y = vec[pocz].second;
  231.     calc_wynik();
  232.     calc_max_wynik();
  233.  
  234.     vec.push_back(make_pair(0,0));
  235.     vec.push_back(make_pair(0,0));
  236.     vec.push_back(make_pair(0,0));
  237.     vec.push_back(make_pair(0,0)); ///DLA BEZPIECZENSTWA - JESLI ODWOLA SIE DO INDEKSU LEKKO POZA ZAKRESEM, TO NIC SIE NIE STANIE
  238. //return 0;
  239.     while(konc <= 2*n)
  240.     {
  241.         ///ZWIEKSZ KONIEC
  242.        // cout<<endl;
  243.         //cout<<"ZWIEKSZAM KONIEC: "<<konc+1<<endl;
  244.  
  245.         konc++;
  246.         add_to_sum(konc);
  247.  
  248.         if(pocz>n&& konc>n) ///CZASEM JEST W STANIE UCIAC CZAS O PRAWIE 50%
  249.             {cout<<max_wynik; return 0;}
  250.  
  251.  
  252.         if(konc-pocz>=n) ///JAK KOM. LINIJKA 9
  253.         {
  254.            // cout<<"USUWAM POCZ, NOWY: "<<pocz+1<<endl;
  255.             remove_from_sum(pocz);
  256.             pocz++;
  257.             remove_from_sum(konc);
  258.             konc--;
  259.             calc_wynik();
  260.             calc_max_wynik();
  261.         }
  262.  
  263.         else{
  264.             ///USUWAJ POCZATEK TAK DLUGO JAK TRZEBA
  265.             while((pole_skierowane(vec[pocz], vec[konc]) > 0 && pocz!=konc)) ///POLE MOZE BYC ROWNE 0, ALE TYLKO W WYPADKU,
  266.             {
  267.                 remove_from_sum(pocz);
  268.             // cout<<"USUWAM POCZATEK, NOWY:"<<pocz+1<<endl;
  269.                 pocz++;
  270.                 remove_from_sum(konc);
  271.                 konc--;
  272.                 calc_wynik();
  273.                 calc_max_wynik();
  274.                 //cout<<"WYNIK: "<<wynik<<endl;
  275.             }
  276.  
  277.             //  cout<<"akt_x: "<<akt_x<<" akt_y: "<<akt_y<<endl;
  278.             calc_wynik();
  279.             calc_max_wynik();
  280.         }
  281.  
  282.  
  283.     }
  284.  
  285.     cout<<max_wynik;
  286.  
  287.     return 0;
  288. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement