Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- struct point {
- point(int x, int y);
- int x;
- int y;
- double dist(point p) {
- return sqrt(double((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y)));
- }
- bool operator<(const point P) const {
- if (x != P.x) {
- return x < P.x;
- }
- else {
- return y < P.y;
- }
- }
- bool operator!=(const point P) const {
- return P.x != x || P.y != y;
- }
- bool operator==(const point P) const {
- return P.x == x && P.y == y;
- }
- void print() {
- cout << x << " " << y << endl;
- }
- };
- int vectorMult(point a, point b, point c) {
- return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
- }
- int square(vector<point> &shell) {
- int sum = 0;
- for (int i = 2; i < shell.size(); ++i) {
- sum += vectorMult(shell[0], shell[i - 1], shell[i]);
- }
- return (sum);
- }
- double perim(vector<point> &shell) {
- double answer = 0;
- for (int i = 1; i < shell.size(); ++i) {
- answer += shell[i].dist(shell[i - 1]);
- }
- answer += shell[0].dist(shell[shell.size() - 1]);
- return answer;
- }
- int squareWithoutI(vector<point> &shell, int i, int sum) {
- if (i != 0) {
- return sum - vectorMult(shell[0], shell[i - 1], shell[i]) -
- vectorMult(shell[0], shell[i], shell[i + 1]) +
- vectorMult(shell[0], shell[i - 1], shell[i + 1]);
- }
- else {
- return sum - vectorMult(shell[shell.size() - 1], shell[0], shell[1]);
- }
- }
- int main() {
- /*freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- */
- int n = 0;
- cin >> n;
- while (n != 0) {
- vector<point> arrayPoints;
- for (int i = 0; i < n; ++i) {
- int x, y;
- cin >> x >> y;
- arrayPoints.push_back(point(x, y));
- }
- sort(arrayPoints.begin(), arrayPoints.end());
- int fl = 0;
- int answer = 0;
- /* for(int i = 0; i < arrayPoints.size(); ++i){
- arrayPoints[i].print();
- }
- cout << endl;
- */
- vector<point> up, down;
- up.push_back(arrayPoints[0]);
- up.push_back(arrayPoints[1]);
- down.push_back(arrayPoints[arrayPoints.size() - 1]);
- down.push_back(arrayPoints[arrayPoints.size() - 2]);
- for (int i = 2; i < arrayPoints.size(); ++i) {
- while (up.size() >= 2 && vectorMult(up[up.size() - 2], up[up.size() - 1], arrayPoints[i]) <= 0) {
- up.erase(up.end());
- }
- up.push_back(arrayPoints[i]);
- }
- for (int i = arrayPoints.size() - 2; i >= 0; --i) {
- while (down.size() >= 2 && vectorMult(down[down.size() - 2], down[down.size() - 1], arrayPoints[i]) <= 0) {
- down.erase(down.end());
- }
- down.push_back(arrayPoints[i]);
- }
- vector<point> shell;
- shell = up;
- for (int i = 1; i < down.size() - 1; ++i) {
- shell.push_back(down[i]);
- }
- int sum = answer = square(shell);
- int currentPointNumber = 0;
- for (int i = 1; i < up.size() - 1; ++i) {
- vector<point> added;
- added.push_back(up[i - 1]);
- currentPointNumber++;
- if (arrayPoints[currentPointNumber] == up[i]) {
- currentPointNumber++;
- }
- added.push_back(arrayPoints[currentPointNumber]);
- if (arrayPoints[currentPointNumber] != up[i + 1]) {
- currentPointNumber++;
- }
- while (up[i + 1] != arrayPoints[currentPointNumber]) {
- if (arrayPoints[currentPointNumber] == up[i]) {
- currentPointNumber++;
- }
- if (arrayPoints[currentPointNumber] == up[i + 1]) {
- break;
- }
- while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
- added.erase(added.end());
- }
- if (arrayPoints[currentPointNumber] != up[i]) {
- added.push_back(arrayPoints[currentPointNumber]);
- }
- currentPointNumber++;
- }
- int squareTmp = -vectorMult(shell[0], up[i - 1], up[i]) - vectorMult(shell[0], up[i], up[i + 1]);
- while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
- added.erase(added.end());
- }
- added.push_back(up[i + 1]);
- for (int j = 1; j < added.size(); ++j) {
- squareTmp += vectorMult(shell[0], added[j - 1], added[j]);
- }
- answer = min(answer, sum + squareTmp);
- while (arrayPoints[currentPointNumber] != up[i]) {
- currentPointNumber--;
- }
- }
- currentPointNumber = arrayPoints.size() - 1;
- for (int i = 1; i < down.size() - 1; ++i) {
- vector<point> added;
- added.push_back(down[i - 1]);
- currentPointNumber--;
- if (arrayPoints[currentPointNumber] == down[i]) {
- currentPointNumber--;
- }
- added.push_back(arrayPoints[currentPointNumber]);
- if (arrayPoints[currentPointNumber] != down[i + 1]) {
- currentPointNumber--;
- }
- while (down[i + 1] != arrayPoints[currentPointNumber]) {
- if (arrayPoints[currentPointNumber] == down[i]) {
- currentPointNumber--;
- }
- if (arrayPoints[currentPointNumber] == down[i + 1]) {
- break;
- }
- while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
- added.erase(added.end());
- }
- if (arrayPoints[currentPointNumber] != down[i]) {
- added.push_back(arrayPoints[currentPointNumber]);
- }
- currentPointNumber--;
- }
- int squareTmp = -vectorMult(shell[0], down[i - 1], down[i]) - vectorMult(shell[0], down[i], down[i + 1]);
- while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
- added.erase(added.end());
- }
- added.push_back(down[i + 1]);
- for (int j = 1; j < added.size(); ++j) {
- squareTmp += vectorMult(shell[0], added[j - 1], added[j]);
- }
- answer = min(answer, sum + squareTmp);
- while (arrayPoints[currentPointNumber] != down[i]) {
- currentPointNumber++;
- }
- }
- //обработка двух крайних точек
- vector<point> tmp = arrayPoints;
- arrayPoints.erase(arrayPoints.begin());
- //первая точка
- {
- vector<point> upTmp, downTmp;
- upTmp.push_back(arrayPoints[0]);
- upTmp.push_back(arrayPoints[1]);
- downTmp.push_back(arrayPoints[arrayPoints.size() - 1]);
- downTmp.push_back(arrayPoints[arrayPoints.size() - 2]);
- for (int i = 2; i < arrayPoints.size(); ++i) {
- while (upTmp.size() >= 2 && vectorMult(upTmp[upTmp.size() - 2], upTmp[upTmp.size() - 1], arrayPoints[i]) <= 0) {
- upTmp.erase(upTmp.end());
- }
- upTmp.push_back(arrayPoints[i]);
- }
- for (int i = arrayPoints.size() - 2; i >= 0; --i) {
- while (downTmp.size() >= 2 && vectorMult(downTmp[downTmp.size() - 2], downTmp[downTmp.size() - 1], arrayPoints[i]) <= 0) {
- downTmp.erase(downTmp.end());
- }
- downTmp.push_back(arrayPoints[i]);
- }
- vector<point> shellTmp;
- shellTmp = upTmp;
- for (int i = 1; i < downTmp.size() - 1; ++i) {
- shellTmp.push_back(downTmp[i]);
- }
- answer = min(square(shellTmp), answer);
- }
- arrayPoints = tmp;
- //последняя точка
- arrayPoints.erase(arrayPoints.end());
- {
- vector<point> upTmp, downTmp;
- upTmp.push_back(arrayPoints[0]);
- upTmp.push_back(arrayPoints[1]);
- downTmp.push_back(arrayPoints[arrayPoints.size() - 1]);
- downTmp.push_back(arrayPoints[arrayPoints.size() - 2]);
- for (int i = 2; i < arrayPoints.size(); ++i) {
- while (upTmp.size() >= 2 && vectorMult(upTmp[upTmp.size() - 2], upTmp[upTmp.size() - 1], arrayPoints[i]) <= 0) {
- upTmp.erase(upTmp.end());
- }
- upTmp.push_back(arrayPoints[i]);
- }
- for (int i = arrayPoints.size() - 2; i >= 0; --i) {
- while (downTmp.size() >= 2 && vectorMult(downTmp[downTmp.size() - 2], downTmp[downTmp.size() - 1], arrayPoints[i]) <= 0) {
- downTmp.erase(downTmp.end());
- }
- downTmp.push_back(arrayPoints[i]);
- }
- vector<point> shellTmp;
- shellTmp = upTmp;
- for (int i = 1; i < downTmp.size() - 1; ++i) {
- shellTmp.push_back(downTmp[i]);
- }
- answer = min(square(shellTmp), answer);
- }
- cout << fixed << setprecision(2) << double(answer) / 2 << endl;
- cin >> n;
- }
- return 0;
- }
- point::point(int x, int y) {
- this->x = x;
- this->y = y;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement