Submission #936068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
936068	2024-03-01T05:50:38 Z	cryan	Mobile (BOI12_mobile)	C++17	Compilation error	0 ms	0 KB

mobile

Then, we can imagine a line perpendicular to the line segment formed by these two stations that passes through the midpoint. Everything on the left side is closer to $a$, and everything on the right side is closer to $b$.

Thus, the maximum point is at the point where the perpendicular line intersects the highway! We only have to get the answer from these critical points, and since there are only two stations that could be closest to it, we can compute them in $\mathcal{O}(1)$.

![Maximum Point](<baltic-12-mobile/perpendicular.png>)

This intersection can be represented by $\frac{b_x^2 + b_y^2 - a_x^2 - a_y^2}{2(b_x - a_x)}$.

From here on, we'll refer to this point as $p(a, b)$, where $a$ and $b$ are stations.

</Spoiler>

Now, let's consider cases where there exist unnecessary stations.

Without loss of generality, let's assume all points are above the y-axis, and $a_x < b_x < c_x$.

### Case 1: $p(a, b) < p(b, c)$

In this arrangement, all stations are the closest to some points on the highway, so we should keep them.

![Case 1](<baltic-12-mobile/case1.png>)

### Case 2: $p(a, b) > p(b, c)$

Note how this creates a cross, which makes $b$ useless. All points on the highway are now closer to $a$ or $c$. To find the maximum point here, we can just remove $b$, and recalculate for $p(a, c)$.

![Case 2](<baltic-12-mobile/case2.png>)

Since we only remove the most recent stations, this motivates the use of a [stack](/gold/stacks) to perform these removals/additions in $\mathcal{O}(1)$.

## Implementation

**Time Complexity**: $\mathcal{O}(N)$

<LanguageSection>
<CPPSection>

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Point {
	double x, y;
};

/**
 * @return the intersection of the perpendicular line that
 * crosses the midpoint of Points a & b with the highway
 */
double max_point(const Point &a, const Point &b) {
	return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) /
	       (2 * b.x - 2 * a.x);
}
/** @return the euclidean distance between points a & b */
double dist(const Point &a, const Point &b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
	int n, l;
	cin >> n >> l;

	deque<Point> stck;
	for (int i = 0; i < n; i++) {
		Point cur;
		cin >> cur.x >> cur.y;
		cur.y = abs(cur.y);

		// always take the one with the lowest y coord
		if ((int)stck.size() && stck.back().x == cur.x) {
			if (cur.y >= stck.back().y) {
				continue;
			} else if (cur.y < stck.back().y) {
				stck.pop_back();
			}
		}

		// find "crosses"
		while ((int)stck.size() > 1 && max_point(stck[(int)stck.size() - 2], stck.back()) > max_point(stck.back(), cur)) {
			stck.pop_back();
		}

		stck.push_back(cur);
	}

	// out of bounds
	while ((int)stck.size() > 1 && max_point(stck[0], stck[1]) < 0) {
		stck.pop_front();
	}

	while ((int)stck.size() > 1 && max_point(stck[(int)stck.size() - 2], stck.back()) > l) {
		stck.pop_back();
	}

	double ans = 0;
	for (int x = 0; x < (int)stck.size(); x++) {
		// get critical points stck[x] is in charge of 
		Point left = {0, 0};
		Point right {l, 0};

		if (x) { left.x = max_point(stck[x], stck[x - 1]); }
		if (x < (int)stck.size() - 1) { right.x = max_point(stck[x], stck[x + 1]); }

		if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) { continue; }

		ans = max({ans, dist(stck[x], left), dist(stck[x], right)});
	}

	cout << fixed << setprecision(6) << ans << endl;
}

Compilation message

mobile.cpp:3:244: error: stray '\' in program
    3 | Thus, the maximum point is at the point where the perpendicular line intersects the highway! We only have to get the answer from these critical points, and since there are only two stations that could be closest to it, we can compute them in $\mathcal{O}(1)$.
      |                                                                                                                                                                                                                                                    ^
mobile.cpp:7:42: error: stray '\' in program
    7 | This intersection can be represented by $\frac{b_x^2 + b_y^2 - a_x^2 - a_y^2}{2(b_x - a_x)}$.
      |                                          ^
mobile.cpp:9:17: warning: missing terminating ' character
    9 | From here on, we'll refer to this point as $p(a, b)$, where $a$ and $b$ are stations.
      |                 ^
mobile.cpp:9:17: error: missing terminating ' character
    9 | From here on, we'll refer to this point as $p(a, b)$, where $a$ and $b$ are stations.
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:13:9: warning: missing terminating ' character
   13 | Now, let's consider cases where there exist unnecessary stations.
      |         ^
mobile.cpp:13:9: error: missing terminating ' character
   13 | Now, let's consider cases where there exist unnecessary stations.
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:15:32: warning: missing terminating ' character
   15 | Without loss of generality, let's assume all points are above the y-axis, and $a_x < b_x < c_x$.
      |                                ^
mobile.cpp:15:32: error: missing terminating ' character
   15 | Without loss of generality, let's assume all points are above the y-axis, and $a_x < b_x < c_x$.
      |                                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:17:1: error: stray '##' in program
   17 | ### Case 1: $p(a, b) < p(b, c)$
      | ^~
mobile.cpp:17:3: error: stray '#' in program
   17 | ### Case 1: $p(a, b) < p(b, c)$
      |   ^
mobile.cpp:23:1: error: stray '##' in program
   23 | ### Case 2: $p(a, b) > p(b, c)$
      | ^~
mobile.cpp:23:3: error: stray '#' in program
   23 | ### Case 2: $p(a, b) > p(b, c)$
      |   ^
mobile.cpp:29:138: error: stray '\' in program
   29 | Since we only remove the most recent stations, this motivates the use of a [stack](/gold/stacks) to perform these removals/additions in $\mathcal{O}(1)$.
      |                                                                                                                                          ^
mobile.cpp:31:1: error: stray '##' in program
   31 | ## Implementation
      | ^~
mobile.cpp:33:23: error: stray '\' in program
   33 | **Time Complexity**: $\mathcal{O}(N)$
      |                       ^
mobile.cpp:38:1: error: stray '`' in program
   38 | ```cpp
      | ^
mobile.cpp:38:2: error: stray '`' in program
   38 | ```cpp
      |  ^
mobile.cpp:38:3: error: stray '`' in program
   38 | ```cpp
      |   ^
mobile.cpp:1:1: error: 'Then' does not name a type
    1 | Then, we can imagine a line perpendicular to the line segment formed by these two stations that passes through the midpoint. Everything on the left side is closer to $a$, and everything on the right side is closer to $b$.
      | ^~~~
mobile.cpp:3:256: error: expected unqualified-id before numeric constant
    3 | Thus, the maximum point is at the point where the perpendicular line intersects the highway! We only have to get the answer from these critical points, and since there are only two stations that could be closest to it, we can compute them in $\mathcal{O}(1)$.
      |                                                                                                                                                                                                                                                                ^
mobile.cpp:3:256: error: expected ')' before numeric constant
    3 | Thus, the maximum point is at the point where the perpendicular line intersects the highway! We only have to get the answer from these critical points, and since there are only two stations that could be closest to it, we can compute them in $\mathcal{O}(1)$.
      |                                                                                                                                                                                                                                                               ~^
      |                                                                                                                                                                                                                                                                )
mobile.cpp:7:78: error: expected unqualified-id before '{' token
    7 | This intersection can be represented by $\frac{b_x^2 + b_y^2 - a_x^2 - a_y^2}{2(b_x - a_x)}$.
      |                                                                              ^
mobile.cpp:7:92: error: '$' does not name a type
    7 | This intersection can be represented by $\frac{b_x^2 + b_y^2 - a_x^2 - a_y^2}{2(b_x - a_x)}$.
      |                                                                                            ^
mobile.cpp:29:150: error: expected unqualified-id before numeric constant
   29 | Since we only remove the most recent stations, this motivates the use of a [stack](/gold/stacks) to perform these removals/additions in $\mathcal{O}(1)$.
      |                                                                                                                                                      ^
mobile.cpp:29:150: error: expected ')' before numeric constant
   29 | Since we only remove the most recent stations, this motivates the use of a [stack](/gold/stacks) to perform these removals/additions in $\mathcal{O}(1)$.
      |                                                                                                                                                     ~^
      |                                                                                                                                                      )
mobile.cpp:33:37: error: expected constructor, destructor, or type conversion before '$'
   33 | **Time Complexity**: $\mathcal{O}(N)$
      |                                     ^
In file included from /usr/include/c++/10/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/10/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:402:26: error: 'std::size_t' has not been declared
  402 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope
  403 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid
  403 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
/usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1360 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1360:46: error: template argument 1 is invalid
 1360 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/10/type_traits:1360:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1362:26: error: 'std::size_t' has not been declared
 1362 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/10/type_traits:1363:21: error: '_Size' was not declared in this scope
 1363 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/10/type_traits:1363:27: error: template argument 1 is invalid
 1363 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/10/type_traits:1364:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1364 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1364:65: error: template argument 1 is invalid
 1364 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/10/type_traits:1364:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1368:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1368 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1368:65: error: template argument 1 is invalid
 1368 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/10/type_traits:1368:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1373:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1373 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1373:46: error: template argument 1 is invalid
 1373 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/10/type_traits:1373:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1375:42: error: 'std::size_t' has not been declared
 1375 |   template<typename _Tp, unsigned _Uint, std::size_t _Size>
      |                                          ^~~
/usr/include/c++/10/type_traits:1376:23: error: '_Size' was not declared in this scope
 1376 |     struct extent<_Tp[_Size], _Uint>
      |                       ^~~~~
/usr/include/c++/10/type_traits:1376:36: error: template argument 1 is invalid
 1376 |     struct extent<_Tp[_Size], _Uint>
      |                                    ^
/usr/include/c++/10/type_traits:1377:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1377 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/include/c++/10/type_traits:1378:24: error: '_Size' was not declared in this scope
 1378 |           _Uint == 0 ? _Size : extent<_Tp,
      |                        ^~~~~
/usr/include/c++/10/type_traits:1379:28: error: template argument 1 is invalid
 1379 |           _Uint - 1>::value>
      |                            ^
/usr/include/c++/10/type_traits:1379:28: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1384:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1384 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from mobile.cpp:39:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,