Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <utility>
- #include <ctime>
- #include <cctype>
- #include <cstdlib>
- #include <cassert>
- #include <functional>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <iomanip>
- #include <string>
- #include <stack>
- #include <queue>
- #include <bitset>
- #include <fstream>
- using namespace std;
- struct pt {
- int x, y;
- };
- bool cmp (pt a, pt b) {
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- }
- bool cw (pt a, pt b, pt c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
- }
- bool ccw (pt a, pt b, pt c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
- }
- double square(pt pt1, pt pt2, pt pt3) {
- double s = abs(0.5*((pt1.x - pt3.x)*(pt2.y - pt3.y) - (pt2.x - pt3.x)*(pt1.y - pt3.y)));
- return s;
- }
- double dist (pt pt1, pt pt2, pt pt3) {
- int a = pt1.y - pt2.y;
- int b = pt1.x - pt2.x;
- int c = -pt1.x * (pt2.y - pt1.y) + pt1.y * (pt2.x - pt1.x);
- // ะก = -X1* (Y2 โ Y1) + Y1*(X2 โX1)
- return (abs(a*pt3.x + b*pt3.y + c) / sqrt (a*a + b*b));
- }
- double Fsquare (const vector<pt> & fig)
- {
- double res = 0;
- for (unsigned i=0; i<fig.size(); i++)
- {
- pt p1 = i ? fig[i-1] : fig.back(),
- p2 = fig[i];
- res += (p1.x - p2.x) * (p1.y + p2.y);
- }
- return fabs (res) / 2;
- }
- vector <pt> exter, inter, unused, allpt, used;
- pt last;
- void convex_hull (vector <pt> & a) {
- if (a.size() == 1) return;
- sort (a.begin(), a.end(), &cmp);
- pt p1 = a[0], p2 = a.back();
- vector <pt> up, down;
- up.push_back (p1);
- down.push_back (p1);
- for (size_t i=1; i < a.size(); ++i) {
- if (i==a.size()-1 || cw (p1, a[i], p2)) {
- while (up.size() >= 2 && !cw (up[up.size()-2], up[up.size()-1], a[i])){
- last = up [up.size() - 1];
- unused.push_back (last);
- up.pop_back();
- }
- up.push_back (a[i]);
- }
- if (i==a.size()-1 || ccw (p1, a[i], p2)) {
- while (down.size() >= 2 && !ccw (down[down.size()-2], down[down.size()-1], a[i])) {
- last = down [down.size() - 1];
- unused.push_back (last);
- down.pop_back();
- }
- down.push_back (a[i]);
- }
- }
- a.clear();
- for (size_t i = 0; i < up.size(); ++i)
- a.push_back (up[i]);
- for (size_t i = down.size() - 2; i > 0; --i)
- a.push_back (down[i]);
- up.clear(); down.clear();
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n; cin >> n;
- for (int i = 0; i < n; ++i) {
- int x, y;
- pt p;
- cin >> x >> y;
- p.x = x; p.y = y;
- allpt.push_back(p);
- exter.push_back(p);
- }
- convex_hull(exter);
- if (exter.size() == n) {
- cout << -1;
- return 0;
- }
- cout << "exter" << '\n';
- for (pt now: exter) {
- cout << now.x << " " << now.y << '\n';
- }
- bool flag = true, check1 = true;
- for (int j = 0; j < unused.size(); ++j) {
- for (int i = 0; i < exter.size()-1; ++i) {
- if (square (exter[i], exter[i+1], unused[j]) == 0) {
- used.push_back(unused[j]);
- flag = false;
- break;
- }
- }
- if (flag) {
- inter.push_back(unused[j]);
- check1 = false;
- }
- }
- if (check1) {
- cout << -1;
- return 0;
- }
- convex_hull(inter);
- cout << "inter" << '\n';
- for (pt now: inter) {
- cout << now.x << " " << now.y << '\n';
- }
- cout << "used" << '\n';
- for (pt now: used) {
- cout << now.x << " " << now.y << '\n';
- }
- double fS = Fsquare (exter);
- cout << "Full " << fS << '\n';
- double temp = 1e9;
- int fixL;
- int m = exter.size();
- for (int i = 0; i < exter.size(); ++i) {
- double S = square(exter[i%m], exter[(i+1)%m], inter[0]);
- if (S < temp && S != 0) {
- fixL = i;
- temp = square(exter[i%m], exter[(i+1)%m], inter[0]);
- }
- }
- double ans = 1e9;
- for (int i = 1; i < inter.size(); ++i) {
- ans = min(ans, temp);
- int k = fixL;
- while (square (exter[(k+1)%m], exter[(k+2)%m], inter[i]) < temp){
- ++k;
- }
- if (square (exter[k%m], exter[(k+1)%m], inter[i]) != 0) {
- temp = square (exter[k%m], exter[(k+1)%m], inter[i]);
- fixL = k;
- }
- }
- ans = min(ans, temp);
- temp = ans;
- cout << "Part " << temp << '\n';
- cout << 2*(fS - temp);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement