7 माह पहले

Educational Round #10 — Editorial

Read the input sequence of numbers until the end of the file. The variable $c$ stores the count of numbers, and the variable $s$ stores their sum.

c = s = 0;
while (scanf("%d", &x) == 1)
{
  c++; 
  s = s + x;
}

Print the count of numbers and their sum.

printf("%d %d\n", c, s);

Open problem

Read the input number $n$ .

scanf("%d", &n);

Compute $a = ⌊ n ⌋$ a = \lfloor \sqrt{n} \rfloor.

a = (int)sqrt(n);

If $a \cdot a = n$ a \cdot a = n, then the number $n$ is a perfect square.

if (a * a == n) printf("%d\n", a);
else puts("No");

Open problem

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k.

long long Cnk(long long n, long long k)
{
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

The main part of the program. Read the value of $n$ .

scanf("%lld", &n);

Compute and print the answer.

res = Cnk(2*n, n);
printf("%lld\n", res);

Open problem

The function PowMod computes the value of $x^{n} m o d m$ x^n~mod~m.

int PowMod(int x, int n, int m)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
  return (x * PowMod(x, n - 1, m)) % m;
}

Read the input data.

scanf("%d %d",&a,&n);

Compute $x = 2^{n - 1} m o d 4000$ x = 2^{n - 1}~mod~4000. And after that, compute and print the final answer:

r es = a^{x} m o d 10000

res = a^x~mod~10000

x = PowMod(2,n-1,4000);
res = PowMod(a,x,10000);
printf("%d\n",res);

Eolymp #4416. Testing System

Young programmer Sasha wrote his first testing system. He was so excited that it successfully compiled that he decided to invite his school friends to his own contest.

However, at the end of the round, it turned out that the system could not sort the teams in the results table. Help Sasha implement this sorting.

Teams are ordered according to ICPC rules:

By the number of solved problems in descending order;
If the number of solved problems is the same, sort by penalty time in ascending order;
If all the previous criteria are equal, sort by team number in ascending order.

Input. The first line contains the number of teams $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) participating in the contest. In the $i$ -th of the following $n$ lines, the number of solved problems $s$ ( $0 \leq s \leq 100$ 0 \le s \le 100) and the penalty time $t$ ( $0 \leq t \leq 1 0^{5}$ 0 \le t \le 10^5) for the team with number $i$ are given.

Output. Print $n$ integers — the team numbers in sorted order.

Open problem

Declare a team structure — an ICPC competition participant, including the team number, penalty time, and number of solved problems.

struct person
{
  int id, penalty_time, problems;
} *acm;

Implement the function cmp — a comparator for sorting the competition participants.

int cmp(person a, person b)
{

Sort by the number of solved problems in descending order.

  if (a.problems != b.problems) return a.problems > b.problems;

If the number of solved problems is equal, sort by penalty time in ascending order.

  if (a.penalty_time != b.penalty_time) 
    return a.penalty_time < b.penalty_time;

If all previous criteria are equal, sort by team number in ascending order.

  return a.id < b.id;
}

The main part of the program. Allocate memory for the array of teams.

scanf("%d",&n);
acm = new person[n];

Read the data about the teams.

for (i = 0; i < n; i++)
{
  scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
  acm[i].id = i + 1;
}

Sort the teams according to the given conditions.

sort(acm,acm+n,cmp);

Print the team numbers in the order of their placement in the results table.

for (i = 0; i < n; i++)
  printf("%d",acm[i].id);
printf("\n");

delete[] acm;

Algorithm implementation — vector

Declare a team structure — an ICPC competition participant, including the team number, penalty time, and number of solved problems.

struct person
{
  int id, penalty_time, problems;
};

Declare an array of teams $a c m$ .

vector<person> acm;

Implement the function cmp — a comparator for sorting the competition participants.

int cmp(person a, person b)
{

Sort by the number of solved problems in descending order.

  if (a.problems != b.problems) return a.problems > b.problems;

If the number of solved problems is equal, sort by penalty time in ascending order.

  if (a.penalty_time != b.penalty_time) 
    return a.penalty_time < b.penalty_time;

If all previous criteria are equal, sort by team number in ascending order.

  return a.id < b.id;
}

The main part of the program. Read the input data.

scanf("%d",&n);
acm.resize(n);
for (i = 0; i < n; i++)
{
  scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
  acm[i].id = i + 1;
}

C++

Sort the teams according to the given conditions.

sort(acm.begin(),acm.end(),cmp);

Print the team numbers in the order of their placement in the results table.

for (i = 0; i < n; i++)
  printf("%d ",acm[i].id);
printf("\n");

Algorithm implementation — build-in comparator

#include <cstdio>
#include <algorithm>
using namespace std;

int n, i, ptr;
struct person
{
  int id, penalty_time, problems;
  int operator< (const person &a) const
  {
    if (problems != a.problems) return problems > a.problems;
    if (penalty_time != a.penalty_time)
      return penalty_time < a.penalty_time;
    return id < a.id;
  }
} *acm;

int main(void)
{
  scanf("%d",&n);
  acm = new person[n];

  for (i = 0; i < n; i++)
  {
    scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
    acm[i].id = i + 1;
  }

  sort(acm,acm+n);
  
  for (i = 0; i < n; i++)
    printf("%d ",acm[i].id);
  printf("\n");
  delete[] acm;
  return 0;
}

C++

Eolymp #5730. YAPTCHA

The Faculty of Mathematics encountered a problem. Due to the large number of automated programs browsing their web pages, it was decided to restrict access to their scientific articles.

To gain access, one must now demonstrate their knowledge — namely, solve a mathematical problem.

However, the test turned out to be too difficult not only for graduate students, but even for some professors. Therefore, the faculty needs to develop a program that automatically solves this problem.

Visitors to the main page of the Faculty of Mathematics are given the following task: for a given positive integer $n$ , compute the value

S_{n} = k = 1 \sum n ⌊ \frac{( 3 k + 6 )! + 1}{3 k + 7} - ⌊ \frac{( 3 k + 6 )!}{3 k + 7} ⌋ ⌋,

S_n = \sum_{k = 1}^n \left\lfloor \frac{(3k + 6)! + 1}{3k + 7} - \left\lfloor \frac{(3k + 6)!}{3k + 7} \right\rfloor \right\rfloor,

where $⌊ x ⌋$ denotes the greatest integer less than or equal to $x$ .

Input. The first line contains the number of queries $t (t \leq 1 0^{6})$ t~(t \le 10^6).

Each of the following $t$ lines contains one integer $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6).

Output. For each query, print the value of $S_{n}$ S_n on a separate line.

Open problem

Let $m = 3 k + 7$ m = 3k + 7. Then the given expression can be rewritten in the form:

S_{n} = m = 10, m = 1 (m o d 3) \sum 3 n + 7 ⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋,

S_n = \sum_{m = 10, m = 1~(mod~3)}^{3n + 7} \left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor,

Wilson's Theorem. If $m$ is a prime number, then

(m - 1)! = - 1 (m o d m)

(m - 1)! = -1~(mod~m)

That is,

(m - 1)! + 1 = 0 (m o d m)

(m - 1)! + 1 = 0~(mod~m)

Therefore, if $m$ is prime, the number $\frac{( m - 1 )! + 1}{m}$ \frac{(m-1)!+1}{m} is an integer.

At the same time,

⌊ \frac{( m - 1 )!}{m} ⌋ = ⌊ \frac{( m - 1 )! + 1}{m} - \frac{1}{m} ⌋ = \frac{( m - 1 )! + 1}{m} - 1

\left\lfloor \frac{(m-1)!}{m} \right\rfloor = \left\lfloor \frac{(m - 1)! + 1}{m} - \frac{1}{m} \right\rfloor = \frac{(m - 1)! + 1}{m} - 1

Then the entire expression equals

⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋ = \frac{( m - 1 )! + 1}{m} - (\frac{( m - 1 )! + 1}{m} - 1) = 1

\left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor = \frac{(m - 1)! + 1}{m} - \left( \frac{(m - 1)! + 1}{m} - 1 \right) = 1

If $m$ is a composite number, then

(m - 1)! = 0 (m o d m),

(m - 1)! = 0~(mod~m),

because among its factors there are all the divisors of $m$ .

In this case, the number

\frac{( m - 1 )!}{m}

\frac{(m-1)!}{m}

is an integer.

Then the entire expression equals

⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋ = ⌊ \frac{( m - 1 )!}{m} + \frac{1}{m} - \frac{( m - 1 )!}{m} ⌋ = ⌊ \frac{1}{m} ⌋ = 0

\left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor = \left\lfloor \frac{(m - 1)!}{m} + \frac{1}{m} - \frac{(m - 1)!}{m} \right\rfloor = \left\lfloor \frac{1}{m} \right\rfloor = 0

Therefore, to compute $S_{n}$ S_n, it is enough to count the number of prime numbers of the form $3 k + 7$ 3k + 7 for $1 \leq k \leq n$ 1 \le k \le n.

Using the Sieve of Eratosthenes, we build the array $u se d$ , where:

u se d [i] = {1, 0, if i is prime, if i is composite .

used[i] = \begin{cases} 1, & \text{if } i \text{ is prime}, \\ 0, & \text{if } i \text{ is composite}. \end{cases}

Then, using the array $u se d$ , construct the array $a$ , which stores information about prime numbers of the form $3 i + 7$ 3i + 7:

a [i] = {1, 0, if 3 i + 7 is prime, if 3 i + 7 is composite .

a[i] = \begin{cases} 1, & \text{if } 3i + 7 \text{ is prime}, \\ 0, & \text{if } 3i + 7 \text{ is composite}. \end{cases}

Now

S_{n} = a [1] + a [2] + \dots + a [n]

S_n = a[1] + a[2] + … + a[n]

Since the problem contains many test cases, to answer each in constant time, we build the prefix sums:

p [i] = a [1] + a [2] + \dots + a [i]

p[i] = a[1] + a[2] + … + a[i]

Now, to solve the problem for any given value of $n$ , it is enough to print $p [n]$ .

Example

Let $m = 7$ m = 7 be a prime number. Then

⌊ \frac{6 ! + 1}{7} - ⌊ \frac{6 !}{7} ⌋ ⌋ = ⌊ \frac{721}{7} - ⌊ \frac{720}{7} ⌋ ⌋ = ⌊ 103 - ⌊ 102 \frac{6}{7} ⌋ ⌋ = ⌊ 103 - 102 ⌋ = 1

\left\lfloor \frac{6!+1}{7} - \left\lfloor \frac{6!}{7} \right\rfloor \right\rfloor = \left\lfloor \frac{721}{7} - \left\lfloor \frac{720}{7} \right\rfloor \right\rfloor = \left\lfloor 103 - \left\lfloor 102 \frac{6}{7} \right\rfloor \right\rfloor = \left\lfloor 103 - 102 \right\rfloor = 1

Let $m = 6$ m = 6 be a composite number. Then

⌊ \frac{5 ! + 1}{6} - ⌊ \frac{5 !}{6} ⌋ ⌋ = ⌊ \frac{121}{6} - ⌊ \frac{120}{6} ⌋ ⌋ = ⌊ 20 + \frac{1}{6} - 20 ⌋ = ⌊ \frac{1}{6} ⌋ = 0

\left\lfloor \frac{5!+1}{6} - \left\lfloor \frac{5!}{6} \right\rfloor \right\rfloor = \left\lfloor \frac{121}{6} - \left\lfloor \frac{120}{6} \right\rfloor \right\rfloor = \left\lfloor 20 + \frac{1}{6} - 20 \right\rfloor = \left\lfloor \frac{1}{6} \right\rfloor = 0

Let's compute the answer for $n = 10$ n = 10. Consider all numbers of the form $3 k + 7$ 3k + 7, where $1 \leq k \leq 10$ 1 \le k \le 10. Among them, identify the prime numbers.

Among the listed numbers, there are $4$ prime numbers: $13, 19, 31$ and $37$ . Therefore, $S_{10} = 4$ S_{10} = 4.

Let us declare the arrays. Since $n \leq 1 0^{6}$ n \le 10^6, the size of the arrays should be set to $3 n + 7 = 3 \cdot 1 0^{6} + 7$ 3n + 7 = 3 \cdot 10^6 + 7.

#define MAX 3000010
char used[MAX], a[MAX];

The function Init implements the Sieve of Eratosthenes. The array $u se d$ stores information about prime numbers:

u se d [i] = {1, 0, if i is prime, if i is composite .

used[i] = \begin{cases} 1, & \text{if } i \text{ is prime}, \\ 0, & \text{if } i \text{ is composite}. \end{cases}

The array $a$ stores information about prime numbers of the form $3 i + 7$ 3i + 7:

a [i] = {1, 0, if 3 i + 7 is prime, if 3 i + 7 is composite .

a[i] = \begin{cases} 1, & \text{if } 3i + 7 \text{ is prime}, \\ 0, & \text{if } 3i + 7 \text{ is composite}. \end{cases}

void Init()
{
  for (int i = 2; i < MAX; i++)
  {
    if (!used[i])
    {
      if ((i - 7) % 3 == 0)
        a[(i - 7) / 3] = true;
      if (i < sqrt(MAX))
        for (int j = i * i; j < MAX; j += i)
          used[j] = true;
    }
  }
}

C++

The main part of the program. Fill the arrays.

Init();

Compute the prefix sums for the array $a$ :

p [i] = a_{1} + a_{2} + ... + a_{i}

p[i] = a_1 + a_2 + ... + a_i

for (int i = 2; i < MAX; ++i)
  p[i] = p[i - 1] + a[i];

Process the tests sequentially.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

For each value of $n$ print $p [n]$ .

  printf("%d\n", p[n]);
}

Eolymp #7757. Square

Jian-Jia has a piece of metal material and wants to cut a square from it. The material is represented as an $n \times n$ n \times n grid, and cuts can only be made along the grid boundaries.

Each cell of the grid is either usable or defective. Jian-Jia aims to cut the largest possible square that contains no defective cells. After determining the maximum possible size of such a square, he also wants to know how many different ways this square can be cut from the material.

Finally, Jian-Jia reports the product of the maximum size and the number of such possible ways.

Consider a $6 \times 6$ 6 \times 6 material, as shown in the figure below. The black cells are defective. The largest square that can be cut has size $3 \times 3$ 3 \times 3, and there are two possible ways to obtain it (shown as the red and green squares). Therefore, Jian-Jia reports the product $3 \cdot 2 = 6$ 3 \cdot 2 = 6.

Your task is to determine the maximum size of a square that can be cut from the given material, as well as the number of distinct ways to obtain such a square. Output the product of these two values.

Input. The first line contains one integer $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000) — the size of the material.

Each of the next $n$ lines contains $n$ integers. A value of $1$ indicates that the corresponding cell is usable, while $0$ indicates that it is defective.

Output. Print one integer — the product of the size of the largest square without defective cells and the number of its possible positions in the material.

Open problem

Declare the array $d p$ .

#define MAX 1010
int dp[MAX][MAX];

Read the value of $n$ . The variable $s i z e$ stores the side length of the largest square, while $c n t$ stores the number of such squares in the given grid. Initialize the $d p$ array with zeros.

scanf("%d", &n);
memset(dp,0,sizeof(dp));
size = cnt = 0;

Iterate over the elements of the $d p$ array row by row: rows in increasing order, and within each row, columns also in increasing order.

  for(i = 1; i <= n; i++)
  for(j = 1; j <= n; j++)
  {
    scanf("%d",&val);

Assume that all values of the $d p$ array up to cell $(i, j)$ have already been computed. Read the next value $v a l = m [i] [j]$ val = m[i][j]. The input matrix is not stored entirely in memory; instead, it is processed on the fly.

Since the $d p$ array is initially initialized with zeros, when $v a l = 0$ val = 0, the value $d p [i] [j]$ dp[i][j] automatically remains zero.

    if (val == 1)
    {
      dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;

Update the values of $s i z e$ and $c n t$ based on the current square of size $d p [i] [j]$ dp[i][j].

      if (dp[i][j] == size) cnt++;
      if (dp[i][j] > size) {size = dp[i][j]; cnt = 1;}
    }
  }

Print the answer.

printf("%lld\n",1LL * size * cnt);

Eolymp #6828. Bread Sorting

Michael works in a bakery. At the end of each shift, his boss asks him to sort the loaves of bread in a certain order. However, she cannot decide exactly what that order should be — according to Michael's observations, it seems to be different every day.

Michael has been working at the bakery for some time and has learned a clever trick with his wooden bread paddle. He can scoop up three adjacent loaves with the paddle and toss them into the air so that when they land, the rightmost loaf moves to the leftmost position, while the other two loaves shift one position to the right. In other words, he can perform a cyclic right rotation on any subsequence of three consecutive loaves.

Before the end of the shift, his colleagues have already placed the bread in one long line. Michael wants to sort the loaves using his paddle trick. He can pick up any three consecutive loaves in the line, rotate them as described, and put them back. However, sometimes it does not matter how many times he uses the paddle — sorting the bread into the order required by his boss may simply be impossible.

Input. The first line contains an integer $n (3 \leq n \leq 1 0^{5})$ n~(3 \le n \le 10^5). Then two lines follow:

the first line contains a permutation of the integers from $1$ to $n$ , representing the current order of the loaves.
the second line contains a permutation of the integers from $1$ to $n$ , representing the order of the loaves required by the boss.

Output. Print "Possible" if Michael can use his paddle to sort the loaves into the order required by his boss. Otherwise, print "Impossible".

Open problem

The paddle trick performs the following permutation of the loaves:

(a c b a c b)

\begin{pmatrix} a & b & c \\ c & a & b \end{pmatrix}

It can be represented as two swaps of adjacent elements:

(a, b, c) \to (a, c, b) \to (c, a, b)

(a, b, c) → (a, c, b) → (c, a, b)

Each swap of adjacent elements changes the parity of the permutation. Therefore, this operation on the loaves preserves the parity of the permutation.

It is possible to sort the loaves in the order required by Michael's boss only if the parities of the permutations coincide.

A linear solution to the problem is based on the fact that two permutations have the same parity if and only if the parity of the number of cycles in their decompositions is the same.

Lemma. Consider the following fact from permutation theory:

p a r i t y o f a p er m u t a t i o n = (n - n u mb er o f cy c l es) m o d 2

parity~of~a~permutation = (n - number~of~cycles)~mod~2

Therefore, to check the parity one can:

decompose the permutation into cycles;
count the number of cycles.

If two permutations have the same parity of the number of cycles, then their permutation parities coincide.

Intuitively, this follows from the fact that each cycle of length $k$ can be constructed from $k - 1$ k - 1 swaps of elements; therefore, the total number of swaps is equal to

n - n u mb er o f cy c l es

n - number~of~cycles

Example

In the first example, the first permutation contains $2$ inversions, while the second contains $6$ inversions. The number of inversions in both permutations has the same parity.

Let us decompose the permutations into cycles:

$(1, 3, 4, 2) = (1) (3, 4, 2)$ (1, 3, 4, 2) = (1) (3, 4, 2);
$(4, 3, 2, 1) = (4, 1) (3, 2)$ (4, 3, 2, 1) = (4, 1) (3, 2);

Both permutations consist of two cycles; therefore, the number of cycles in them also has the same parity.

In the second example, the first permutation contains $0$ inversions, while the second contains $15$ inversions. The number of inversions in these permutations has different parity.

Let us decompose the permutations into cycles:

$(1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6)$ (1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6);
$(6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3)$ (6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3);

The first permutation consists of $6$ cycles, while the second consists of $3$ cycles. Thus, the parity of the number of cycles in these permutations is different.

Declare an array to store the permutation.

#define MAX 100010
int a[MAX];

The function run traverses one cycle of the permutation starting from index $p os$ . At each step, it moves to the next element of the cycle according to the rule $p os \to a [p os]$ pos \to a[pos]. Visited elements are marked with the value $- 1$ to avoid processing them again. Thus, the function completely traverses one cycle of the permutation and marks all its elements as already visited.

void run(int pos)
{
  int v;
  while (a[pos] != -1)
  {
    v = a[pos];
    a[pos] = -1;
    pos = v;
  }
}

C++

The function parity computes the parity of the number of cycles in the permutation $a$ , that is, it returns the number of cycles modulo $2$ . The function sequentially scans all positions of the array.

int parity(int *a)
{
  int res = 0;

Sequentially examine all positions of the array.

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

If an element has not yet been visited $(a [i] \neq = - 1)$ (a[i] \ne -1), this means the beginning of a new cycle. In this case, the function $r u n (i)$ is called, which traverses the entire cycle and marks its elements with the value $- 1$ .

    if (a[i] != -1) 
    {
      run(i);

After traversing the cycle, the counter $r es$ is increased by $1$ .

      res++;
    }

Return the parity of the number of cycles.

  return res % 2;
}

The main part of the program. Read the first permutation. During input, each value is decreased by $1 (a [i] - -)$ 1~(a[i]--) to convert from $1$ -based indexing $(1.. n)$ to the more convenient $0$ -based indexing $(0.. n - 1)$ (0 .. n - 1).

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;

In the variable $p 1$ , compute the parity of the number of cycles in the permutation $a$ .

p1 = parity(a);

Read the second permutation. In the variable $p 2$ , compute the parity of the number of cycles in the permutation $a$ .

for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;
p2 = parity(a);

Compare the parities of the number of cycles in the two permutations and print the result.

if (p1 == p2) printf("Possible\n");
else printf("Impossible\n");

Eolymp #2299. Theodore Roosevelt

"Theodore Roosevelt" — the flagship of the Kukuland fleet. The sworn enemies of Kukuland, the Flat-Earthers, decided to destroy it. They learned that "Theodore Roosevelt" is represented by a convex polygon with $n$ vertices, and the coordinates of all its vertices are known to them. Then they launched $m$ ballistic missiles and recorded the coordinates of their explosion points. According to the calculations of the Flat-Earthers' headquarters, "Theodore Roosevelt" will be destroyed if at least $k$ missiles hit it. Determine whether the Flat-Earthers managed to destroy the ship.

Input. The first line contains integers $n, m$ and $k (3 \leq n \leq 1 0^{5}, 0 \leq k \leq m \leq 1 0^{5})$ k~(3 \le n \le 10^5, 0 \le k \le m \le 10^5). The next $n$ lines contain the coordinates of the polygon vertices in counterclockwise order. The following $m$ lines contain the coordinates of the explosion points. All coordinates are integers with absolute values not exceeding $1 0^{9}$ 10^9.

Output. Print "YES" if at least $k$ points lie inside the polygon, and "NO" otherwise.

Open problem

Let us define a $P o in t$ structure and an array of points.

#define MAX 100001
struct Point
{
  long long x, y;
  Point(long long x = 0, long long y = 0) : x(x), y(y) {}
};
Point p[MAX];

C++

The function angle determines whether the turn made when moving through points $А, B, С$ А, B, С is left or right. To do this, we calculate the corresponding vectors:

A B = (b . x - a . x, b . y - a . y) B C = (c . x - b . x, c . y - b . y)

AB = (b.x - a.x, b.y - a.y) \\ BC = (c.x - b.x, c.y - b.y)

The pseudo-scalar (cross) product of $A B \times B C$ AB \times BC is

b . x - a . x c . x - b . x b . y - a . y c . y - b . y = (b . x - a . x) \cdot (c . y - b . y) - (b . y - a . y) \cdot (c . x - b . x)

\begin{vmatrix} b.x - a.x & b.y - a.y \\ c.x - b.x & c.y - b.y \end{vmatrix} = (b.x - a.x)\cdot(c.y - b.y) - (b.y - a.y)\cdot(c.x - b.x)

The sign of this expression determines the direction of the turn:

Positive value — left turn;
Negative value — right turn;

int angle(Point a, Point b, Point c)
{
  long long q = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
  return (q > 0) - (q < 0); // sgn(q)
}

The function inside returns $t r u e$ if the point $q$ lies inside the polygon.

bool inside(Point q)
{

We choose the first vertex of the polygon as the base.

  Point a = p[1];

If the orientation of the triple $p_{1} p_{n} q$ p_1p_nq is left, or the orientation of the triple $p_{1} p_{2} q$ p_1p_2q is right, then the point $q$ lies outside the angle $p_{n} p_{1} p_{2}$ p_np_1p_2, and therefore outside the polygon.

  if (angle(a, p[2], q) < 0 || angle(a, p[n], q) > 0) return false;

Perform a binary search on the interval $[l; r] = [2; n]$ [l; r] = [2; n]. We look for points $p_{l}$ p_l and $p_{r} (r = l + 1)$ p_r~(r = l + 1) such that the point $q$ lies inside the angle $p_{l} p_{1} p_{r}$ p_lp_1p_r.

  int l = 2, r = n, m;
  while (l + 1 < r)
  {
    m = (l + r) / 2;
    if (angle(a, p[m], q) < 0)
      r = m;
    else
      l = m;
  }
  return angle(p[l], p[r], q) >= 0;
}

C++

The main part of the program. Read the input data.

scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
  scanf("%lld %lld", &x, &y);
  p[i] = Point(x, y);
}

Compute the number of points that lie inside the polygon.

res = 0;
for (int i = 1; i <= m; ++i)
{
  scanf("%lld %lld", &x, &y);
  if (inside(Point(x, y))) res++;
}

Print the answer.

if (res < k) puts("NO"); else puts("YES");

Eolymp #7747. City Horizon

Farmer John has arrived in the city with his cows! During sunset, the cows look at the city skyline and observe beautiful silhouettes formed by rectangular buildings.

The entire skyline is represented by a number line with $n$ buildings. The silhouette of the $i$ -th building extends along the horizon between points $a_{i}$ a_i and $b_{i}$ b_i and has height $h_{i}$ h_i. Determine the total area (in square units) of the silhouette formed by all $n$ buildings.

Input. The first line contains an integer $n (1 \leq n \leq 40000)$ n~(1 \le n \le 40000). Each of the next $n$ lines describes the $i$ -th building with three integers: $a_{i}, b_{i} (1 \leq a_{i} < b_{i} \leq 1 0^{9})$ a_i, b_i~(1 \le a_i < b_i \le 10^9) and $h_{i} (1 \leq h_{i} \leq 1 0^{9})$ h_i~(1 \le h_i \le 10^9).

Output. Print the total area of the city skyline (in square units) formed by all $n$ buildings.

Open problem

To represent a point, we introduce a structure $n o d e$ that stores its $x$ -coordinate, a flag indicating whether it is the start ( $t y p e = 0$ type = 0) or the end ( $t y p e = 1$ type = 1) of a segment, and the height $h$ of the corresponding building.

struct node
{
  int x, type, h;
  node(int x, int type, int h) : x(x), type(type), h(h) {};
};

Define a comparator f for points — sort them in increasing order of their $x$ -coordinates.

int f(node a, node b)
{
  return a.x < b.x;
}

Declare an array of points $E v e n t$ , as well as a multiset $s$ to store the heights of buildings intersecting the current position of the sweep line.

vector<node> Event;
multiset<int, greater<int> > s;

Read the input data. Construct the array of points.

scanf("%d",&n);
for(i = 0; i < n; i++)
{
  scanf("%d %d %d",&left,&right,&height);
  Event.push_back(node(left,0,height));
  Event.push_back(node(right,1,height));
}

C++

Sort the array of points in non-decreasing order of their $x$ -coordinates.

sort(Event.begin(),Event.end(),f);

Accumulate the total area of the city skyline in the variable $r es$ .

res = 0;

Move from left to right over the points in the $E v e n t$ array. For each index $i$ in the $f or$ loop, consider the interval $(E v e n t [i] . x, E v e n t [i + 1] . x)$ (Event[i].x, Event[i + 1].x).

for (i = 0; i < Event.size() - 1; i++)
{

If the point $x_{i}$ x_i is the start of a building, insert the corresponding height into the multiset.

  int h = Event[i].h;
  if (Event[i].type == 0) s.insert(h);

If the point $x_{i}$ x_i is the end of a building, remove the corresponding height from the multiset.

  else s.erase(s.find(h));

If the multiset is not empty, then on the segment between $E v e n t [i] . x$ Event[i].x and $E v e n t [i + 1] . x$ Event[i + 1].x there exists a skyline whose height is equal to the maximum element in $s$ , i.e. $* s . b e g in ()$ *s.begin().

  if (!s.empty())
    res += 1LL * *s.begin() * (Event[i+1].x - Event[i].x);
}

Print the computed area.

printf("%lld\n",res);

Educational Round #10 — Editorial

टिप्पणियाँ