e-olymp 4496. Приключение Незнайки и его друзей

26/06/2019 by Анна Неделева

Задача

Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

Входные данные

В первой строке содержится количество человечков $n$ $(1 \leqslant n \leqslant 10^{6})$ в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают $10^{9}.$ Далее следует количество запросов $m$ $(1 \leqslant m \leqslant 10^{5})$. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число $v$ $(1 \leqslant v \leqslant 10^{9})$ – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа $x$ $(1 \leqslant x \leqslant n)$ и $y$ $(1 \leqslant y \leqslant 10^{9})$ — это значит, что вес человечка, стоящего на позиции $x$, теперь равен $y$.

Выходные данные

Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.

Тесты

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3	3 2 2 0
2	2 1 2 3 1 3 2 1 8 1 3	2 0
3	5 1 3 4 5 6 5 1 7 1 9 2 3 5 1 7 2 3 1	2 3 2
4	1 5 3 1 3 2 1 2 1 3	0 1
5	1 1 2 1 4 1 3	1 1

Код программы

#include <iostream>
using namespace std;

struct tree {
    long * tr;
    tree(int n) {
        tr = new long[4 * n + 1];
    }
    void build(int * arr, int v, int l, int r) {
        if (l == r) tr[v] = arr[l];
        else {
            int mid = (l + r) / 2;
            build(arr, v * 2, l, mid);
            build(arr, v * 2 + 1, mid + 1, r);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) tr[v] = val;
        else {
            int mid = (l + r) / 2;
            if (pos <= mid) update(v * 2, l, mid, pos, val);
            else update(v * 2 + 1, mid + 1, r, pos, val);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    int find(int v, int l, int r, int max) {
        if (l == r)
            return (tr[v] <= max);
        int mid = (l + r) / 2;
        if (tr[v * 2] > max)
            return find(v * 2, l, mid, max);
        else
            return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);
    }
};

int main() {
    int n, m, * arr;
    cin >> n;
    arr = new int[n + 1];
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    tree tr(n);
    tr.build(arr, 1, 1, n);
    cin >> m;
    int com, x, y, v;
    for (int i = 0; i < m; ++i) {
        cin >> com;
        switch (com) {
        case 1:
            {
                cin >> v;
                cout << tr.find(1, 1, n, v) << '\n';
                break;
            }
        case 2:
            {
                cin >> x >> y;
                tr.update(1, 1, n, x, y);
                break;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

struct tree {

long * tr;

tree(int n) {

tr = new long[4 * n + 1];

}

void build(int * arr, int v, int l, int r) {

if (l == r) tr[v] = arr[l];

else {

int mid = (l + r) / 2;

build(arr, v * 2, l, mid);

build(arr, v * 2 + 1, mid + 1, r);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

void update(int v, int l, int r, int pos, int val) {

if (l == r) tr[v] = val;

else {

int mid = (l + r) / 2;

if (pos <= mid) update(v * 2, l, mid, pos, val);

else update(v * 2 + 1, mid + 1, r, pos, val);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

int find(int v, int l, int r, int max) {

if (l == r)

return (tr[v] <= max);

int mid = (l + r) / 2;

if (tr[v * 2] > max)

return find(v * 2, l, mid, max);

else

return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);

}

};

int main() {

int n, m, * arr;

cin >> n;

arr = new int[n + 1];

for (int i = 1; i <= n; ++i) cin >> arr[i];

tree tr(n);

tr.build(arr, 1, 1, n);

cin >> m;

int com, x, y, v;

for (int i = 0; i < m; ++i) {

cin >> com;

switch (com) {

case 1:

{

cin >> v;

cout << tr.find(1, 1, n, v) << '\n';

break;

}

case 2:

{

cin >> x >> y;

tr.update(1, 1, n, x, y);

break;

}

return 0;

}

Решение задачи

Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.

Ссылки

Related Images:

e-olymp 2496. Конкатенация строк

23/05/2019 by Анна Неделева

Задача

Во многих прикладных задачах необходимо осуществлять различные операции со строками. Две достаточно часто встречающиеся операции — это разворот строки и конкатенация двух или нескольких строк.

В результате разворота строки $s$ получается строка $sR$, которая состоит из тех же символов, что и $s$, но идущих в обратном порядке. Например, в результате разворота строки «$abcde$» получается строка «$edcba$». Далее в этой задаче вместо обозначения $sR$ будет использоваться обозначение ($s$).

В результате конкатенации двух строк $s$ и $t$ получается строка $st$, в которой сначала записаны символы строки $s$, а затем — символы строки $t$. Аналогичным образом определяется конкатенация трех, четырех и большего числа строк. Например, при конкатенации строк «$abc$» и «$cda$» получается строка «$abccda$».

Ваша задача — определить результат конкатенации нескольких строк, часть из которых необходимо развернуть.

Входные данные

Состоит из единственной строки, которая содержит только строчные буквы латинского алфавита и круглые скобки. Ее длина не превышает $200$ символов. Эта строка описывает конкатенацию нескольких строк, часть из которых необходимо развернуть.

В заданной строке правее каждой открывающей скобки есть закрывающая, левее каждой закрывающей есть открывающая, причем между соответствующими друг другу открывающей и закрывающей скобками других скобок нет и обязательно есть хотя бы одна буква.

Выходные данные

Выведите результат конкатенации.

Тесты

№	Входные данные	Выходные данные
1	russ(ai)(edocn)cup	russiancodecup
2	(bi).mazurok	ib.mazurok
3	acm.(cpci)	acm.icpc
4	Od(asse)	Odessa
5	(inu)ver(ytis)	university

Код программы(string)

#include <iostream>
using namespace std;

void revers(string & str) {
  char a;
  cin.get(a);
  if (a != ')') revers(str);
  else return;
  str += a;
}

int main() {
  string str = "";
  char a;
  while (cin.get(a))
    if (a == '(') revers(str);
    else str += a;
  cout << str;
  return 0;
}

#include <iostream>

using namespace std;

void revers(string & str) {

char a;

cin.get(a);

if (a != ')') revers(str);

else return;

str += a;

}

int main() {

string str = "";

char a;

while (cin.get(a))

if (a == '(') revers(str);

else str += a;

cout << str;

return 0;

}

Код программы (c-string)

#include <iostream>
using namespace std;

const int N = 200;

void revers(char * res, int &n) {
   char a;
   cin >> a;
   if (a == ')') return;
   else revers(res, n);
   res[n++] = a;
}

int main() {
   char res[N];
   char a;
   int n = 0;
   while (cin >> a) {
      if (a == '(') revers(res, n);
      else res[n++] = a;
   }
   for (int i = 0; i < n; i++)
      cout << res[i];
   return 0;
}

#include <iostream>

using namespace std;

const int N = 200;

void revers(char * res, int &n) {

char a;

cin >> a;

if (a == ')') return;

else revers(res, n);

res[n++] = a;

}

int main() {

char res[N];

char a;

int n = 0;

while (cin >> a) {

if (a == '(') revers(res, n);

else res[n++] = a;

}

for (int i = 0; i < n; i++)

cout << res[i];

return 0;

}

Решение задачи

Перебираем каждый символ входной строки, как только встречаем ‘(‘ рекурсивно запоминаем каждый символ, вплоть до ‘)’. А на выходе из рекурсии добавляем эти символы в результирующую строку. Так как при выходе рекурсия будет выполнять сначала самый поздний свой вызов, а только после этого завершать более ранние, то добавляться символы будут в обратном порядке, что нам и нужно. Повторяем вышеописанные действия до конца данной строки.

Ссылки

Related Images:

e-olymp 4752. Кинотеатр

28/03/2019 by Анна Неделева

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные

В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.

Выходные данные

Выведите одно число — количество учеников, которые в результате пересадки остануться сидеть на тех же местах.

Тесты

№	Входные данные	Выходные данные
1	3 3	3
2	3 4	2
3	6 3	2
4	5 9	5
5	7 5	3

Код программы

#include <iostream>
using namespace std;

int main() {
  int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i][j] = count1++;
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      if (arr[i][j] == count2) result++;
      count2++;
    }
  }
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

arr[i][j] = count1++;

for (int j = 0; j < m; j++) {

for (int i = 0; i < n; i++) {

if (arr[i][j] == count2) result++;

count2++;

}

cout << result << "\n";

}

Код программы с линейным массивом

#include <iostream>
using namespace std;
 
int main() {
  int arr[1000 * 1000], n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i * m + j] = i * m + j;
  for (int j = 0; j < m; j++) 
    for (int i = 0; i < n; i++) 
      if (arr[i * m + j] == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000 * 1000], n, m, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

arr[i * m + j] = i * m + j;

for (int j = 0; j < m; j++)

for (int i = 0; i < n; i++)

if (arr[i * m + j] == j * n + i) result++;

cout << result << "\n";

}

Код программы без массива

#include <iostream>
using namespace std;
 
int main() {
  int n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (i * m + j == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int n, m, result = 0;

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

if (i * m + j == j * n + i) result++;

cout << result << "\n";

}

Решение задачи

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

Related Images:

e-olymp 927. Количество игрушек

14/01/2019 by Анна Неделева

Задача

Задано количество видов игрушек в магазине, количество игрушек каждого вида и стоимость игрушки каждого вида. Определить количество игрушек, стоимость которых меньше $50$ грн.

Входные данные

В первой строке задано количество наличных в прейскуранте видов игрушек $n$ $(0 ≤ n ≤ 1000)$. В следующих $n$ строках задано по $2$ числа через пробел: сначала количество игрушек $a$ $(0 ≤ a ≤ 1000)$ очередного вида и их цена $b$ $(0 < b ≤ 10000)$ в грн.

Выходные данные

Вывести количество игрушек, стоимость которых меньше $50$ грн.

Тесты

№	Входные данные	Выходные данные
1	3 2 100.00 5 23.00 10 22.50	15
2	3 2 10.00 5 2355.00 6 22.50	8
3	4 2 15.00 13 2355.00 10 22.50 1 49.00	13
4	2 2 15.00 13 51.00	2
5	3 3 100.00 5 230.00 7 220.50	0

Код программы

#include <iostream>
using namespace std;
 
int main() {
  int n, count, result = 0;
  long double cost;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> count >> cost;
    if (cost < 50) {
      result += count;
    }
  }
  cout << result;
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count, result = 0;

long double cost;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> count >> cost;

if (cost < 50) {

result += count;

}

cout << result;

return 0;

}

Решение задачи

Если цена за игрушку меньше 50 грн, то вся партия этого вида игрушек удовлетворяет условию.
Считаем количество игрушек во всех таких партиях.

Ссылки

Related Images:

e-olymp 4192. Олимпиада

25/12/2018 by Анна Неделева

Задача

На олимпиаду по информатике прибыло $n$ команд, каждая из которых состоит из $a_i$ мальчиков и $b_i$ девочек $(1 ≤ i ≤ n)$. Для проживания имеются одинаковые комнаты по $m$ мест в каждой. Какое наименшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?

Входные данные

Первая строка содержит числа $n$ и $m$. Каждая следующая из $n$ строк содержит пару чисел $a_i$ , $b_i$ $(1 ≤ i ≤ n)$. Все числовые значения целые неотрицательные и не превышают $100$.

Выходные данные

Вывести наименьшее необходимое количество комнат.

Тесты

№	Входные данные	Выходные данные
1	2 3 2 1 3 2	3
2	3 5 5 8 2 3 6 1	6
3	2 2 1 1 1 3	3
4	4 2 1 3 5 1 2 7 3 1	12
5	7 2 5 6 3 4 2 5 1 3 9 3 8 7 6 4	33

Код программы

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, m, a, b, k = 0, l = 0;
    cin >> n >> m;
    while (n--) {
        cin >> a >> b;
        k += a;
        l += b;
    }
    cout << (k + m - 1) / m + (l + m - 1) / m ;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, m, a, b, k = 0, l = 0;

cin >> n >> m;

while (n--) {

cin >> a >> b;

k += a;

l += b;

}

cout << (k + m - 1) / m + (l + m - 1) / m ;

return 0;

}

Решение задачи

Для решения задачи найдём общее количество мальчиков и девочек, затем по отдельности посчитаем в каком количестве комнат они поместятся, но когда мы целочисленно делим количество детей на вместимость одной комнаты, мы определяем какое количество комнат будет заполнено полностью. Но, если количество детей не кратно количеству комнат, то полученный ответ должен быть на единицу больше. Для этого к количеству детей добавим ещё ровно столько, сколько нужно для того, чтобы ответ стал больше на единицу, то есть $m$, но на один меньше, чтобы при количестве детей кратном ответ был прежний. А после сложим полученные значения.

Ссылки

Related Images:

e-olymp 839. Пересечение отрезков

24/12/2018 by Анна Неделева

Задача

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.

Требуется определить, существует ли у них общая точка.

Входные данные

В первой строке содержатся координаты первого конца первого отрезка, во второй — второго конца первого отрезка, в третьей и четвёртой — координаты концов второго отрезка. Координаты целые и по модулю не превосходят $10000$.

Выходные данные

Вывести слово $Yes$, если общая точка есть, или слово $No$ в противном случае.

Тесты

№	Входные данные	Выходные данные
1	0 0 1 0 1 0 1 1	Yes
2	0 0 1 0 2 0 3 0	No
3	7 4 1 1 1 1 3 2	Yes
4	-9725 -8992 9812 9925 -9999 7011 8122 -9248	Yes
5	-9999 -1 10000 1 0 0 0 1	No

Код программы

С ветвлением:

#include <iostream>
#include <cmath>
#define E 1e-5
using namespace std;

double length(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){
    return (
        abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E
    &&
        abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E
    );
}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return(
        abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E
    ||
        abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E
    ||
        abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E
    ||
        abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E
    );
}

int main() {
    long x1, y1, x2, y2, x3, y3, x4, y4;
    double x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    long long ky1, kx1, b1, ky2, kx2, b2;
    ky1 = y2 - y1;
    ky2 = y4 - y3;
    kx1 = x2 - x1;
    kx2 = x4 - x3;
    b1 = x1 * y2 - x2 * y1;
    b2 = x3 * y4 - x4 * y3;
    if (kx1 * ky2 == kx2 * ky1) {
        if (
            b1 * ky2 != b2 * ky1
        && 
            b1 * kx2 != b2 * kx1
        ) cout << "No";
        else if (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) cout << "Yes";
        else cout << "No";
    } else {
        y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1);
        x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1);
        if (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) cout << "Yes";
        else cout << "No";
    }
    return 0;
}

#include <iostream>

#include <cmath>

#define E 1e-5

using namespace std;

double length(double x1, double y1, double x2, double y2){

return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){

return (

abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E

abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E

);

}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {

return(

abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E

abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E

abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E

abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E

);

}

int main() {

long x1, y1, x2, y2, x3, y3, x4, y4;

double x, y;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

long long ky1, kx1, b1, ky2, kx2, b2;

ky1 = y2 - y1;

ky2 = y4 - y3;

kx1 = x2 - x1;

kx2 = x4 - x3;

b1 = x1 * y2 - x2 * y1;

b2 = x3 * y4 - x4 * y3;

if (kx1 * ky2 == kx2 * ky1) {

if (

b1 * ky2 != b2 * ky1

b1 * kx2 != b2 * kx1

) cout << "No";

else if (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) cout << "Yes";

else cout << "No";

} else {

y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1);

x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1);

if (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) cout << "Yes";

else cout << "No";

}

return 0;

}

без ветвления:

#include <iostream>
#include <cmath>
#define E 1e-5
using namespace std;

double length(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){
    return (
        abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E
    &&
        abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E
    );
}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return(
        abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E
    ||
        abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E
    ||
        abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E
    ||
        abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E
    );
}

int main() {
    long x1, y1, x2, y2, x3, y3, x4, y4;
    double x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    long long ky1, kx1, b1, ky2, kx2, b2;
    ky1 = y2 - y1;
    ky2 = y4 - y3;
    kx1 = x2 - x1;
    kx2 = x4 - x3;
    b1 = x1 * y2 - x2 * y1;
    b2 = x3 * y4 - x4 * y3;
    (kx1 * ky2 == kx2 * ky1) && (
        (
            b1 * ky2 != b2 * ky1
        && 
            b1 * kx2 != b2 * kx1
        ) && (cout << "No")
        || (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes") 
        || (cout << "No")
    ) || (
        y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1),
        x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1),
        (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes")
        || (cout << "No")
    );
    return 0;
}

#include <iostream>

#include <cmath>

#define E 1e-5

using namespace std;

double length(double x1, double y1, double x2, double y2){

return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){

return (

abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E

abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E

);

}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {

return(

abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E

abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E

abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E

abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E

);

}

int main() {

long x1, y1, x2, y2, x3, y3, x4, y4;

double x, y;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

long long ky1, kx1, b1, ky2, kx2, b2;

ky1 = y2 - y1;

ky2 = y4 - y3;

kx1 = x2 - x1;

kx2 = x4 - x3;

b1 = x1 * y2 - x2 * y1;

b2 = x3 * y4 - x4 * y3;

(kx1 * ky2 == kx2 * ky1) && (

(

b1 * ky2 != b2 * ky1

b1 * kx2 != b2 * kx1

) && (cout << "No")

|| (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes")

|| (cout << "No")

) || (

y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1),

x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1),

(is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes")

|| (cout << "No")

);

return 0;

}

Решение задачи

Чтобы проверить пересекаются ли заданные отрезки построим прямые, которым они принадлежат, затем найдём точку их пересечения и проверим принадлежит ли она каждому из отрезков.
Для построения прямых воспользуемся формулой прямой проходящей через две точки и немного её преобразуем:
$\frac{x — x_1}{x_2 — x_1} = \frac{y — y_1}{y_2 — y_1}$ ~ $(x — x_1) \cdot (y_2 — y_1) = (y — y_1) \cdot (x_2 — x_1)$ ~ $x \cdot (y_2 — y_1) — y_2 \cdot x_1 + y_1 \cdot x_1 = y \cdot (x_2 — x_1) — x_2 \cdot y_1 + x_1 \cdot y_1$ ~ $y \cdot (x_2 — x_1) = x \cdot (y_2 — y_1) + x_2 \cdot y_1 — x_1 \cdot y_2$.
Обозначим за $k_x$ множитель при $x$, за $k_y$ множитель при $y$, а всё остальное за $b$. Тогда имеем уравнение вида:
$y \cdot k_y = x \cdot k_x + b$, таких у нас будет 2:

$y \cdot k_{y_1} = x \cdot k_{x_1} + b_1$
$y \cdot k_{y_2} = x \cdot k_{x_2} + b_2$

Теперь рассмотрим несколько случаев:
1. Прямые параллельны, следовательно могут не иметь точки пересечения или совпадать.
Проверим совпадают ли $b_1$ и $b_2$. Так как уравнения не сокращены на НОД, то рассмотрим равенство отношений $b_1$ и $b_2$ на $k_{y_1}$, $k_{x_1}$ и $k_{y_2}$, $k_{x_2}$ соответственно. Если они равны, то прямые совпадают. Иначе не имеют точек пересечения, а следовательно и отрезки тоже не пересекаются.
Когда прямые совпадают, необходимо проверить, что отрезки на этой прямой имеют хоть какую-то общую точку. Каждый из концов каждого отрезка проверим на вхождение в другой. Если такое вхождение есть, то отрезки пересекаются, иначе нет.
2. Прямые не параллельны, а следовательно имеют точку пересечения.
Тогда, решив систему двух линейных уравнений в общем виде получим что:

$x = \frac{b_1 \cdot k_{x_2} — b_2 \cdot k_{x_1}}{k_{y_1} \cdot k_{x_2} — k_{x_1} \cdot k_{y_2}}$
$y = \frac{b_2 \cdot k_{y_1} — b_1 \cdot k_{y_2}}{k_{x_1} \cdot k_{y_2} — k_{y_1} \cdot k_{x_2}}$

Осталось проверить находится ли точка с координатами $(x, y)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.