Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ДОБАВИТЬ В ШАБЛОН:
- 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);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement