1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
struct Sensor
{
long x, y, power;
Sensor(long xx, long yy, long pp = 0):
x(xx), y(yy), power(pp) {}
};
std::vector<Sensor> sensors;
bool isDistressBeacon(const Sensor& c)
{
if (c.x < 0 || c.x > 4000000 || c.y < 0 || c.y > 4000000)
return false;
bool found = true;
uint64_t freq = 0;
for (auto& s : sensors) {
auto dist = std::abs(c.x - s.x) + std::abs(c.y - s.y);
if (dist <= s.power) {
found = false;
break;
}
}
return found;
}
int main()
{
long px, py, bx, by;
std::string line;
std::getline(std::cin, line);
for (; !std::cin.eof(); std::getline(std::cin, line)) {
auto a = sscanf(line.c_str(),
"Sensor at x=%ld, y=%ld: closest beacon is at x=%ld, y=%ld",
&px, &py, &bx, &by);
long power = std::abs(px - bx) + std::abs(py - by);
sensors.emplace_back(px, py, power);
}
for (auto& s : sensors) {
for (long q = 0; q <= (s.power + 1) * 2; ++q) {
auto x = s.x + q - s.power - 1;
auto y = s.y + q;
if (isDistressBeacon(Sensor(x, y))) {
std::cout << x * 4000000 + y << std::endl;
return 0;
}
y -= q * 2;
if (isDistressBeacon(Sensor(x, y))) {
std::cout << x * 4000000 + y << std::endl;
return 0;
}
}
}
return 0;
}
|
