#include #include #include #include using namespace std; using u64 = unsigned long long; struct pos { int x; int y; bool deleted = false; pos operator-(const pos& other) const { return pos{x - other.x, y - other.y}; } double length() const { return hypot(x, y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int nodes; cin >> nodes; vector positions; vector sortedByX; vector sortedByY; positions.reserve(nodes); sortedByX.reserve(nodes); sortedByY.reserve(nodes); for (int i = 0; i < nodes; ++i) { pos p; cin >> p.x >> p.y; positions.push_back(p); sortedByX.push_back(&positions[i]); sortedByY.push_back(&positions[i]); } std::sort(sortedByX.begin(), sortedByX.end(), [](const pos* first, const pos* second) { return first->x < second->x; }); std::sort(sortedByY.begin(), sortedByY.end(), [](const pos* first, const pos* second) { return first->y < second->y; }); int iter = nodes / 4; size_t minX = 0; size_t maxX = nodes-1; size_t minY = 0; size_t maxY = nodes-1; for (int i = 0; i < iter-1; ++i) { while(sortedByX[minX]->deleted) { minX++; } while(sortedByX[maxX]->deleted) { maxX--; } while(sortedByY[minY]->deleted) { minY++; } while(sortedByY[maxY]->deleted) { maxY--; } pos* nextX, *prevX; for (int i2 = minX+1; i2 <= maxX; i2++) { if (!sortedByX[i2]->deleted) { nextX = sortedByX[i2]; break; } } for (int i2 = maxX-1; i2 >= minX; i2--) { if (!sortedByX[i2]->deleted) { prevX = sortedByX[i2]; break; } } sortedByX[minX]->deleted = true; sortedByX[maxX]->deleted = true; if (sortedByX[minX]->x == nextX->x) { nextX->deleted = true; prevX->deleted = true; } else { sortedByY[minY]->deleted = true; sortedByY[maxY]->deleted = true; } } while(sortedByX[minX]->deleted) { minX++; } while(sortedByX[maxX]->deleted) { maxX--; } while(sortedByY[minY]->deleted) { minY++; } while(sortedByY[maxY]->deleted) { maxY--; } pos *topL, *leftB, *rightT; topL = sortedByY[minY]; if (sortedByX[minX]->y == topL->y) { topL = sortedByX[minX]; } leftB = sortedByX[minX]; if (sortedByY[maxY]->x == leftB->x) { leftB = sortedByY[maxY]; } rightT = sortedByX[maxX]; if (sortedByY[minY]->x == rightT->x) { rightT = sortedByY[minY]; } double area = (*topL - *rightT).length() * (*leftB - *topL).length(); int areaInt = (int)round(area); printf("%d\n", areaInt); }