cf

ДОБАВИТЬ В ШАБЛОН:

17.07.22 14:19
Timus №1020: построение выпуклой оболочки - поиск угла ABC по координатам:
double angle(pdd A, pdd B, pdd C) {
    return (B.first - A.first) * (C.second - B.second) - (B.second - A.second) * (C.first - B.first);
    //B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0]
}
19.07.22

1110 функция бинарного возведения в степень, чтобы можно было работать умножать с модулями binary pow(power())

1496 нахождение ключа и перебор map():
if(mp.count(key)) {...}
for (auto i = mp.begin(); i != mp.end(); i++) {
        if (i->second > 1)
            cout << i->first << "\n";
    }

1446
ЧТЕНИЕ СТРОКИ:
#include <string>
getline(cin, str)

ОПАСНОСТЬ! ПОСЛЕ СЧИТЫВАНИЯ cin >> n ПЕРЕД ИСПОЛЬЗОВАНИМ getline() НУЖНО ВЫЗВАТЬ getline() ВПУСТУЮ! ИНАЧЕ ПРОЧТЁТСЯ ПУСТАЯ СТРОКА.

1084
ЗНАМЕНАТЕЛЬ ВСЕГДА В СКОБКИ
1.0 - AB * AB / 2.0 * r * r
НЕ РАВНО
1.0 - AB * AB / (2.0 * r * r)
к делению всегда осторожно

1225 DP:
ВСЕГДА ПРОВЕРЯТЬ НАЧАЛЬНОЕ СОСТОЯНИЕ




03.08.22
ВСОПМНИТЬ СОВЕТ ПРО ПРИВЕДЕНИЕ К (int)
            NEW TODO до ICPC:(2303221556)
            1) Разобраться, как работают структуры в C++(как передаются в функции, объявляются и используются внутри других структур)
            2) Разобраться, как работают массивы и вектора при передаче в функции и возвращении из них в C++
            3) Разобраться, что за типы size_t и почему их нужно приводить к (int):
            4) Как делать двоичный поиск(lower_bound, upper_bound)

            double findSquare(const vector<point> & vertex, const vector<int> & convexHull)
            {
!!ЭТОТ->                // если не сделать явного приведения к типу int, то будет попытка зайти в цикл,
                // т.к. convexHull.size() имеет тип size_t(безнаковое целое),
                // то если convexHull пуст. получим 0-1 = 4294967295
                double S = 0;
                for (int i = 1; i < (int)convexHull.size() - 1; i++)
                {
                    S += findSquare(
                        vertex[convexHull[0]],
                        vertex[convexHull[i]],
                        vertex[convexHull[i + 1]]);
                }

                return Fabs(S / 2);
            }







            TODO EXTRA NOW: 0702221334
            13:34
            1) До 14:00 сделать функцию хэша строки, возвращающую вектор long long с хэшами для каждого префикса и проверить его на выводе.






№1348
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное
РАССТОЯНИЕ ДО ОТРЕЗКА - минимальное и максимальное


double ras(pair<double, double> a, pair<double, double> b) {
    return sqrt((b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second));
}

//ВЕКТОРА ИЗ ОДНОГО КОНЦА ИЛИ В ОДИН КОНЕЦ!!
double orr (pair<double, double> AB, pair<double, double> BC) { //по знаку: тупой или острый угол - если добавить длины в знаменатель, то получится косинус
    return (AB.first * BC.first + AB.second * BC.second);
}
double rastDoOtr(pair<double, double> A, pair<double, double> B, pair<double, double> C, double def = 1.0) {
    //S = (xy - yx)/2 //ab_x bc_y - ab_y bc_x
    pair<double, double> AB = { B.first - A.first, B.second - A.second },
    BC = { C.first - B.first, C.second - B.second },
    CB = { -BC.first, -BC.second},
    AC = { C.first - A.first, C.second - A.second };

    if(orr(AB, CB) >= 0 && orr(AC, BC) >= 0) //<= 0 - значит тупоугольный
        return (abs(AB.first * BC.second - AB.second * BC.first)) / ras(B, C);
    return def * 2 * 1e9; //если не можем рассматривать расстояние как что-то нужное
}

//A -> BC
double minSegDist(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
    return min(min(ras(A, B), ras(A, C)), rastDoOtr(A, B, C));
}
double maxSegDist(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
    return max(max(ras(A, B), ras(A, C)), rastDoOtr(A, B, C, -1.0));
}

int main() {
    pair<double, double> B, C, A;
    double D;
    cout << fixed << setprecision(10);
    //На вход: отрезок BC, точка A и длина верёвки от точки A.
    //На выход: длина, на которую нужно удлинить верёвку, чтобы достать до одной точки отрезка '\n' чтобы достать до каждой точки отрезка
    cin >> B.first >> B.second >> C.first >> C.second >> A.first >> A.second >> D;
    cout << max(0.0, minSegDist(A, B, C) - D) << '\n' << max(0.0, maxSegDist(A, B, C) - D);
    return 0;
}

=====================================================
=====================================================
=====================================================
=====================================================
=====================================================







22.08.22
1402 BIG INT(long arithmetic)
Вставить реализацию длинной арифметики
struct Bigint {
    string a;
    int sign;

    Bigint(){}
    void operator = (string b) {
        a= (b[0]=='-' ? b.substr(1) : b);
        reverse(a.begin(), a.end());
        (*this).Remove0(b[0]=='-' ? -1 : 1);
    }
    Bigint(string x) {(*this)=x;}
    Bigint(ll x) {(*this)=to_string(x);}
    void operator = (ll x){*this=to_string(x);}

    char operator[](int i){return a[i];}
    int size() {return a.size();}
    Bigint inverseSign() {sign*=-1; return (*this);}

    Bigint Remove0(int newSign) {
        sign = newSign;
        for(int i=a.size()-1; i>0 && a[i]=='0'; i--) a.pop_back();
        if(a.size()==1 && a[0]=='0') sign=1;
        return (*this);
    }

    bool operator == (Bigint x) {return sign==x.sign && a==x.a;}
    bool operator == (string x) {return *this==Bigint(x);}
    bool operator == (ll x)     {return *this==Bigint(x);}
    bool operator != (Bigint x) {return !(*this==x);}
    bool operator != (string x) {return !(*this==x);}
    bool operator != (ll x)     {return !(*this==x);}

    bool operator < (Bigint b) {
        if (sign!=b.sign) return sign<b.sign;
        if(a.size()!=b.size()) return a.size()*sign<b.size()*sign;
        for(int i=a.size()-1; i>=0; i--)
            if(a[i] != b[i]) return a[i]<b[i];
        return false;
    }
    bool operator <  (string x) {return *this<Bigint(x);}
    bool operator <  (ll x)     {return *this<Bigint(x);}
    bool operator <= (Bigint b) {return *this==b || *this<b;}
    bool operator <= (string b) {return *this==b || *this<b;}
    bool operator <= (ll b)     {return *this==b || *this<b;}
    bool operator >  (Bigint b) {return !(*this==b || *this<b);}
    bool operator >  (string x) {return !(*this==x || *this<x);}
    bool operator >  (ll b)     {return !(*this==b || *this<b);}
    bool operator >= (Bigint b) {return *this==b || *this>b;}
    bool operator >= (string b) {return *this==b || *this>b;}
    bool operator >= (ll b)     {return *this==b || *this>b;}

    Bigint operator + (Bigint b) {
        if(sign != b.sign) return (*this)-b.inverseSign();
        Bigint sum;
        for(int i=0, carry=0; i<a.size() || i<b.size() || carry; i++){
            if (i<a.size()) carry+=a[i]-'0';
            if (i<b.size()) carry+=b[i]-'0';
            sum.a += (carry % 10 + 48);
            carry /= 10;
        }
        return sum.Remove0(sign);
    }
    Bigint operator +  (string x) {return *this+Bigint(x);}
    Bigint operator +  (ll x)     {return *this+Bigint(x);}
    Bigint operator ++ (int) {*this+=1; return *this-1;}
    Bigint operator ++ ()    {*this+=1; return *this;}
      void operator += (Bigint x) {*this = *this+x;}
      void operator += (string x) {*this = *this+x;}
      void operator += (ll x)     {*this = *this+x;}


    Bigint operator - ( Bigint b ) {
        if(sign != b.sign) return (*this)+b.inverseSign();
        if(*this < b) return (b - *this).inverseSign();
        Bigint sub;
        for(int i=0,borrow=0; i<a.size(); i++) {
            borrow = a[i]-borrow-(i<b.size() ? b.a[i] : '0');
            sub.a += borrow>=0 ? borrow+'0' : borrow + 58;
            borrow = borrow>=0 ? 0:1;
        }
        return sub.Remove0(sign);
    }
    Bigint operator - (string x) {return *this-Bigint(x);}
    Bigint operator - (ll x)     {return *this-Bigint(x);}
    Bigint operator -- (int) {*this-=1; return *this+1;}
    Bigint operator -- ()    {*this-=1; return *this;}
      void operator -= (Bigint x) {*this = *this-x;}
      void operator -= (string x) {*this = *this-x;}
      void operator -= (ll x)     {*this = *this-x;}

    Bigint operator * (Bigint b) {
        Bigint mult("0");
        for(int i=0, k=a[i]; i<a.size(); i++, k=a[i]) {
            while(k-- -'0') mult=mult+b;
            b.a.insert(b.a.begin(),'0');
        }
        return mult.Remove0(sign * b.sign);
    }
    Bigint operator * (string x) {return *this*Bigint(x);}
    Bigint operator * (ll x)     {return *this*Bigint(x);}
      void operator *= (Bigint x) {*this = *this*x;}
      void operator *= (string x) {*this = *this*x;}
      void operator *= (ll x)     {*this = *this*x;}

    Bigint operator / (Bigint b) {
        if(b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0');
        Bigint c("0"), d;
        for(int j=0; j<a.size(); j++) d.a += "0";
        int dSign = sign*b.sign; b.sign=1;
        for(int i=a.size()-1; i>=0; i--) {
            c.a.insert(c.a.begin(),'0');
            c=c+a.substr(i,1);
            while(!(c<b)) c=c-b, d.a[i]++;
        }
        return d.Remove0(dSign);
    }
    Bigint operator / (string x) {return *this/Bigint(x);}
    Bigint operator / (ll x)     {return *this/Bigint(x);}
      void operator /= (Bigint x) {*this = *this/x;}
      void operator /= (string x) {*this = *this/x;}
      void operator /= (ll x)     {*this = *this/x;}

    Bigint operator % (Bigint b) {
        if( b.size()==1 && b[0]=='0') b.a[0]/=(b[0]-'0') ;
        Bigint c("0");
        int cSign = sign*b.sign; b.sign=1;
        for( int i=a.size()-1; i>=0; i-- ) {
            c.a.insert( c.a.begin(),'0');
            c = c+a.substr(i,1);
            while(!(c<b)) c=c-b;
        }
        return c.Remove0(cSign);
    }
    Bigint operator % (string x) {return *this%Bigint(x);}
    Bigint operator % (ll x)     {return *this%Bigint(x);}
      void operator %= (Bigint x) {*this = *this%x;}
      void operator %= (string x) {*this = *this%x;}
      void operator %= (ll x)     {*this = *this%x;}

    void print() {
        if(sign==-1) putchar('-');
        for(int i=a.size()-1; i>=0; i--) putchar(a[i]);
    }
    friend istream& operator >>(istream &in,Bigint &x){
        string s; in>>s; x=s; return in;
    }
    friend ostream& operator <<(ostream &out,Bigint &x){
        if(x.sign==-1) putchar('-');
        for(int i=x.size()-1; i>=0; i--)
            putchar(x[i]);
        return out;
    }

    friend Bigint pow(Bigint base, Bigint pw){
        Bigint ans=1;
        while(pw!=0){
            if(pw%2 !=0) ans*=base;
            base*=base, pw/=2;
        }
        return ans;
    }
    friend Bigint pow(Bigint a, Bigint b,Bigint mod) {
        if (b==0) return Bigint(1);
        Bigint tmp=pow(a,b/2,mod);
        if ((b%2)==0) return (tmp*tmp)%mod;
        else return (((tmp*tmp)%mod)*a)%mod;
    }
    friend Bigint sqrt(Bigint x) {
        Bigint ans=x,tmp=(x+1)/2;
        while (tmp<ans) ans=tmp, tmp=(tmp+x/tmp)/2;
        return ans;
    }
    friend Bigint gcd(Bigint a,Bigint b){
        return a%b==0 ? b : gcd(b, a%b);
    }
    friend Bigint lcm(Bigint a,Bigint b){
        return a/gcd(a,b);
    }
};

Bigint binpow(Bigint a, Bigint b) {
    if (b <= 0)
        return 1;
    Bigint res = binpow(a, b / 2);
    if (b % 2 != 0)
        return res * res * a;
    else
        return res * res;
}




1352
ТАБЛИЦА БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ!!!

https://dpva.ru/Guide/GuideMathematics/GuideMathematicsFiguresTables/SimpleFigures/SimpleFiguresPrint/




2005
АЛГОРИТМ ДЕЙКСТРЫ
#include <bits/stdc++.h>
using namespace std;
struct Edge{
  int vertex;
  int wt;
  Edge(int d,int w){
    vertex = d;
    wt = w;
  }
};
struct Compare{
  bool operator()(Edge &e1,Edge &e2){
    return (e1.wt < e2.wt)? false:true ;
  }
};
struct Graph{
  int V;
  vector<Edge> *edges;
  Graph(int V){
    this->V = V;
    edges = new vector<Edge>[V];
  }
  void addEdge(int u,int v,int wt){
    edges[u].push_back(Edge(v,wt));
    edges[v].push_back(Edge(u,wt));
  }
  int *dijkstras(int src){
    int *dist = new int[V];
    bool visited[V];
    for(int i=0;i<V;i++){
      dist[i] = INT_MAX;
      visited[i] = false;
    }
    dist[src] = 0;
    priority_queue<Edge,vector<Edge>,Compare> pq;
    pq.push(Edge(src,dist[src]));
    while(!pq.empty()){
      Edge curr = pq.top();
      pq.pop();
      if(!visited[curr.vertex])
        visited[curr.vertex] = true;
      else
        continue;
      for(Edge e : edges[curr.vertex]){
        if(!visited[e.vertex]){
          if((curr.wt + e.wt) < dist[e.vertex]){
            dist[e.vertex] = curr.wt + e.wt;
            pq.push(Edge(e.vertex,dist[e.vertex]));
          }
        }
      }
    }
    return dist;
  }
};

int main(){
  int V,E;
  cin>>V>>E;
  Graph g(V);
  for(int i=0;i<E;i++){
    int u,v,wt;
    cin>>u>>v>>wt;
    g.addEdge(u,v,wt);
  }
  int *dist = g.dijkstras(0);
  for(int i=0;i<V;i++){
    cout<<0<<"  ->  "<<i<<" = "<<dist[i]<<endl;
  }
  return 0;
}













ФУНКЦИИ с числами С Volga Camp

https://pastebin.com/G2QCvSqp

            #include "bits/stdc++.h"

using namespace std;

vector<long long> p;
vector<int> md;
long long sum_d = 0;


long long sum_mu = 1;
vector<int> mu;
long long sum_fi = 1;
vector<int> fi;
vector<int> al1;
vector<long long> pal1;

long long sum_si0 = 1;
vector<int> si0;

long long sum_si1 = 1;
vector<long long> si1;


signed main() {
    int n;
    cin >> n;

    md.resize(n + 1);
    mu.resize(n + 1);
    fi.resize(n + 1);
    pal1.resize(n + 1);
    al1.resize(n + 1);
    si0.resize(n + 1);
    si1.resize(n + 1);


    mu[1] = 1;
    fi[1] = 1;
    pal1[1] = 0;
    al1[1] = 0;
    si0[1] = 1;
    si1[1] = 1;

    iota(md.begin(), md.end(), 0);
    for (long long x = 2; x < n + 1; ++x) {
        if (md[x] == x)
            p.emplace_back(x);
        for (int i = 0; i < p.size() and p[i] <= x and p[i] * x <= n; ++i) {
            md[p[i] * x] = p[i];
        }


        int y = x / md[x];
        if (md[y] == md[x]) {
            al1[x] = al1[y] + 1;
            pal1[x] = pal1[y] * md[x];
            mu[x] = 0;
            si0[x] = si0[y] + (si0[y] / (al1[y] + 1));
            si1[x] = (pal1[x] * md[x] - 1) * si1[y] / (pal1[x] - 1);
            fi[x] = md[x] * fi[y];
        } else {
            al1[x] = 1;
            pal1[x] = md[x];
            mu[x] = -mu[y];
            si0[x] = si0[y] * 2;
            si1[x] = (1 + md[x]) * si1[y];
            fi[x] = (md[x] - 1) * fi[y];
        }
        sum_mu += mu[x];
        sum_d += md[x];
        sum_fi += fi[x];
        sum_si0 += si0[x];
        sum_si1 += si1[x];
    }
    cout << sum_d << ' ' << sum_si0 << ' ' << sum_si1 << ' ' << sum_fi << ' ' << sum_mu;
    return 0;
}










29.08.22 16:09

1193
tuple<int, int, int> tp = {1, 2, 3}; // то же самое, что и pair(и для сортировки, и для сравнения), только из 3-х элементов
ПОЛУЧИТЬ ЭЛЕМЕНТЫ ТРОЙКИ: get<0>(tp), get<1>(tp), get<2>(tp)
или начиная с C++17:
auto [aa, bb, cc] = tp;









11.03.23 15:06 Тульская олимпиада(квалификационный раунд)

Уравнение плоскости по трём точкам.

void equation_plane(double x1, double y1,
    double z1, double x2,
    double y2, double z2,
    double x3, double y3, double z3)
{
    double a1 = x2 - x1, b1 = y2 - y1, c1 = z2 - z1, a2 = x3 - x1, b2 = y3 - y1, c2 = z3 - z1;
    double a = b1 * c2 - b2 * c1, b = a2 * c1 - a1 * c2, c = a1 * b2 - b1 * a2, d = (-a * x1 - b * y1 - c * z1);
    //a b c d

}











25.03.23 14:26
Заполнить вектор от a до n+a-1:
#include <numeric>
iota(vc.begin(), vc.end(), a);