Tutorial•11 hours ago

Educational Round #10 — Editorial

Let us consider $2 n$ objects $a_{1}, ..., a_{2 n}$ and find the number of ways to choose $n$ objects from these $2 n$ .

Divide the set into two parts of $n$ objects each:

{a_{1}, a_{2}, ..., a_{n}} an d {a_{n + 1}, ..., a_{2 n}}

To choose $n$ objects from the $2 n$ , we can select $k (k \leq n)$ objects from the left half and $n - k$ objects from the right half.

According to the multiplication principle, the number of ways to make such a selection is

C_{n}^{k} \cdot C_{n}^{n - k} = (C_{n}^{k})^{2}

Since $k$ can take all values from $0$ to $n$ , the sum of all possibilities is

k = 0 \sum n (C_{n}^{k})^{2},

which equals the number of ways to choose $n$ objects from $2 n$ , that is $C_{2 n}^{n}$ . Thus, we obtain the formula:

(C_{n}^{0})^{2} + (C_{n}^{1})^{2} + (C_{n}^{2})^{2} + ... + (C_{n}^{n})^{2} = C_{2 n}^{n}

Example

For $n = 3$ the answer is $(C_{3}^{0})^{2} + (C_{3}^{1})^{2} + (C_{3}^{2})^{2} + (C_{3}^{3})^{2} = 1^{2} + 3^{2} + 3^{2} + 1^{2} = 20$

At the same time $C_{6}^{3} = \frac{6 !}{3 ! \cdot 3 !} = \frac{4 \cdot 5 \cdot 6}{6} = 20$ .

Open problem

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}$ ) participating in the contest. In the $i$ -th of the following $n$ lines, the number of solved problems $s$ ( $0 \leq s \leq 100$ ) and the penalty time $t$ ( $0 \leq t \leq 1 0^{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;
}

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;
}

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} ⌋ ⌋,

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})$ .

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

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

Open problem

Let $m = 3 k + 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} ⌋ ⌋,

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

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

That is,

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

Therefore, if $m$ is prime, the number $\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

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

If $m$ is a composite number, then

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

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

In this case, the number

\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

Therefore, to compute $S_{n}$ , it is enough to count the number of prime numbers of the form $3 k + 7$ for $1 \leq k \leq 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 .

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

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

Now

S_{n} = a [1] + a [2] + \dots + 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]

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

Example

Let $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

Let $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

Let's compute the answer for $n = 10$ . Consider all numbers of the form $3 k + 7$ , where $1 \leq k \leq 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$ .

Let us declare the arrays. Since $n \leq 1 0^{6}$ , the size of the arrays should be set to $3 n + 7 = 3 \cdot 1 0^{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 .

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

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

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;
    }
  }
}

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}

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]);
}

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$ 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$ material, as shown in the figure below. The black cells are defective. The largest square that can be cut has size $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$ .

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)$ — 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

Let us define a two-dimensional array $d p$ , where

$d p [i] [j]$ denotes the side length of the largest square consisting entirely of ones, with its bottom-right corner at cell $(i, j)$ .

Let the array $m$ represent the given grid.

Base cases

If $m [i] [j] = 0$ (the cell is defective), then no square can end at cell $(i, j)$ . Therefore, $d p [i] [j] = 0$ ;
If the cell lies on the boundary ( $i = 0$ or $j = 0$ ) and $m [i] [j] = 1$ , then only a square of size $1$ is possible. Therefore, $d p [i] [j] = 1$

DP transitions

Assume that $m [i] [j] = 1$ . Consider the following cases:

Suppose that $m [i - 1] [j] = m [i] [j - 1] = k$ . Then the value of $d p [i] [j]$ depends on the state of the cell $m [i - k] [j - k]$ :
- If $m [i - k] [j - k] = 1$ , then the entire square with corners at $(i - k, j - k)$ and $(i, j)$ consists only of ones, so $d p [i] [j] = k + 1$ .
- If $m [i - k] [j - k] = 0$ , then the square cannot be extended, and $d p [i] [j] = k$ .
If $m [i - 1] [j] \neq = m [i] [j - 1]$ , then the value of $d p [i] [j]$ is determined as

d p [i] [j] = min (d p [i - 1] [j], d p [i] [j - 1]) + 1

Summarizing the above, we obtain the general formula:

d p [i] [j] = min (d p [i - 1] [j], d p [i] [j - 1], d p [i - 1] [j - 1]) + 1

Example

Consider the second test case. Let us construct the $d p$ array for it.

There are two largest squares of size $3 \cdot 3$ . The product of the maximum square size and the number of its occurrences is $3 \cdot 2 = 6$ .

Declare the array $d p$ .

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

Read the value of $n$ . The variable $s i ze$ 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]$ . 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$ , the value $d p [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 ze$ and $c n t$ based on the current square of size $d p [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);

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})$ . 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)

It can be represented as two swaps of adjacent elements:

(a, b, c) \to (a, c, b) \to (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 cyc l es) m o d 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$ swaps of elements; therefore, the total number of swaps is equal to

n - n u mb er o f cyc l es

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)$ ;
$(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)$ ;
$(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]$ . 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;
  }
}

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)$ , 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 $res$ 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] - -)$ to convert from $1$ -based indexing $(1.. n)$ to the more convenient $0$ -based indexing $(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");

"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})$ . 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}$ .

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

Open problem

Consider the problem of determining whether a point belongs to a convex polygon.

Suppose the vertices of the polygon are given in counterclockwise order: $p_{1}, p_{2}, ..., p_{n}$ . Fix the vertex $p_{1}$ . Then all other vertices are ordered around it by polar angle.

Draw rays from point $p_{1}$ through the remaining vertices (i.e., the diagonals of the polygon). We can now apply binary search to find an edge $p_{i} p_{i + 1}$ such that the orientations of the triples of points $p_{1} p_{i} q$ and $p_{1} p_{i + 1} q$ are different.

Thus, we determine the sector (triangle) in which the point $q$ may lie.

After the angle $p_{i} p_{1} p_{i + 1}$ containing the point $q$ is found, we can check in constant time whether the points $p_{1}$ and $q$ lie on the same side of the line $p_{i} p_{i + 1}$ . For this, the orientation of the triple $p_{i} p_{i + 1} q$ must be left (since the orientation of $p_{i} p_{i + 1} p_{1}$ is left, as the polygon vertices are given in counterclockwise order).

At the beginning of the algorithm, it is also necessary to check boundary cases: if the orientation of the triple $p_{1} p_{n} q$ is left or the orientation of the triple $p_{1} p_{2} q$ is right, then the point $q$ lies outside the polygon.

Turn direction. Consider moving from point $А$ to point $В$ , and then from $В$ to point $С$ . The turn is considered left (counterclockwise) if the vector (pseudo-scalar) product $A B \times BC > 0$ , and right if $A B \times BC < 0$ .

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];

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

A B = (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 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)

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$ is left, or the orientation of the triple $p_{1} p_{2} q$ is right, then the point $q$ lies outside the angle $p_{n} p_{1} p_{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]$ . We look for points $p_{l}$ and $p_{r} (r = l + 1)$ such that the point $q$ lies inside the angle $p_{l} p_{1} p_{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;
}

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");

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}$ and $b_{i}$ and has height $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)$ . 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})$ and $h_{i} (1 \leq h_{i} \leq 1 0^{9})$ .

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

Open problem

Consider all points — the $x$ -coordinates of the beginnings and ends of the buildings — and sort them in increasing order. For each such point, we store:

its coordinate,
its type (start of a building — $t y p e = 0$ , end — $t y p e = 1$ ),
the height of the corresponding building.

Next, process these points sequentially from left to right.

We maintain a multiset $s$ that stores the heights of buildings that have already started but have not yet ended at the current moment. This multiset allows us to efficiently determine the maximum height among the active buildings.

Let the current point have coordinate $x_{i}$ , and the next point $x_{i + 1}$ . Let $h$ denote the maximum element in the multiset $s$ (if the set is empty, assume $h = 0$ ). Then, on the interval $[x_{i}, x_{i + 1}]$ ), the maximum height of the silhouette is $h$ , and the contribution to the area is

(x_{i + 1} - x_{i}) \cdot h

Add this value to the total area.

After that, update the multiset:

if the point $x_{i}$ is the start of a building, insert its height into $s$ ;
if it is the end of a building, we remove the corresponding height from $s$ .

The order of processing events with the same $x$ -coordinate (starts and ends of buildings) does not affect the correctness of the solution, since segments of zero length do not contribute to the area.

Example

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$ ) or the end ( $t y p e = 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));
}

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 $res$ .

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)$ .

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

If the point $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}$ 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$ and $E v e n t [i + 1] . x$ there exists a skyline whose height is equal to the maximum element in $s$ , i.e. $* s . b e g in ()$ .

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

Print the computed area.

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

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server