#include #include #include #include bool used[200100] = {false}; struct Point{ int index; long long number; long long x; long long y; Point() = default; Point(int index, long long x, long long y, long long number){ this->x = x; this->y = y; this->index = index; this->number = number; } /* bool operator>(const Point& sec) const{ return number > sec.number; } */ bool operator<(const Point& sec) const{ return number < sec.number; } }; using namespace std; int main() { int N; cin >> N; std::vector horizontal; std::vector vertical; horizontal.reserve(N); vertical.reserve(N); for (int i = 0; i < N; i++) { long long x, y; cin >> x >> y; horizontal.push_back(Point(i, x, y, x)); vertical.push_back(Point(i, x, y, y)); } std::sort(horizontal.begin(), horizontal.end()); std::sort(vertical.begin(), vertical.end()); /* for (int i = 0; i < N; i++) { std::cout << horizontal[i].x << "," << horizontal[i].y << std::endl; } std::cout << std::endl; */ int startX = 0; int endX = N - 1; int startY = 0; int endY = N - 1; int maxCount = N / 4 - 1; for(int k = 0; k < maxCount; k++){ int firstIndex = -1; int secondIndex = -1; int g = startX; while(firstIndex < 0 || secondIndex < 0){ if(used[horizontal[g].index] == false){ if(firstIndex < 0) firstIndex = g; else secondIndex = g; } g++; } if(horizontal[firstIndex].x == horizontal[secondIndex].x){ // std::cout << "ALIGN" << std::endl; //Aligned int thirdIndex = -1; int forthIndex = -1; g = endX; while(thirdIndex < 0 || forthIndex < 0){ if(used[horizontal[g].index] == false){ if(thirdIndex < 0) thirdIndex = g; else forthIndex = g; } g--; } used[horizontal[firstIndex].index] = true; used[horizontal[secondIndex].index] = true; used[horizontal[thirdIndex].index] = true; used[horizontal[forthIndex].index] = true; startX = std::max(firstIndex, secondIndex) + 1; endX = std::min(thirdIndex, forthIndex) - 1; startY += 2; endY -= 2; } else{ // std::cout << "NOT" << std::endl; secondIndex = -1; g = endX; while(secondIndex < 0){ if(used[horizontal[g].index] == false){ secondIndex = g; } g--; } int thirdIndex = -1; g = startY; while(thirdIndex < 0){ if(used[horizontal[g].index] == false){ thirdIndex = g; } g++; } int forthIndex = -1; g = endY; while(forthIndex < 0){ if(used[horizontal[g].index] == false){ forthIndex = g; } g--; } used[horizontal[firstIndex].index] = true; used[horizontal[secondIndex].index] = true; used[vertical[thirdIndex].index] = true; used[vertical[forthIndex].index] = true; startX = firstIndex + 1; endX = secondIndex - 1; startY = thirdIndex + 1; endY = forthIndex - 1; } } // std::cout << std::endl; // std::cout << std::endl; Point p[4]; int h = 0; for(int i = startX; i <= endX; i++){ if(used[horizontal[i].index] == false){ // std::cout << i << " : " << horizontal[i].x << " " << horizontal[i].y << std::endl; p[h++] = horizontal[i]; } } int X1 =p[1].x - p[0].x; int Y1 =p[1].y - p[0].y; int X2 =p[2].x - p[0].x; int Y2 =p[2].y - p[0].y; int _X = Y1 - Y2; int _Y = X2 - X1; int _Z = X1 * Y2 - X2 * Y1; // std::cout << (unsigned long long)std::sqrt(_X * _X + _Y * _Y + _Z * _Z); std::cout << std::abs(_Z) <