Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- struct pt {
- double 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;
- }
- void Pirimier(vector<pt> pointlist)
- {
- float result(0.0);
- for (int i = 1; i < pointlist.size(); i++)
- {
- result += sqrt(pow((pointlist[i].x - pointlist[i-1].x),2) + pow((pointlist[i].y - pointlist[i-1].y),2));
- }
- result += sqrt(pow((pointlist[pointlist.size() - 1].x - pointlist[0].x),2) + pow((pointlist[pointlist.size() - 1].y - pointlist[0].y),2));
- printf("%f\n",result);
- }
- void Square (vector<pt> pointlist)
- {
- float result(0.0);
- pt M;
- M.x = 0; M.y = 0;
- pt MAi;
- pt MAi_1;
- for (int i = 0; i < pointlist.size()-1; i++)
- {
- MAi.x = pointlist[i].x;
- MAi.y = pointlist[i].y;
- MAi_1.x = pointlist[i+1].x;
- MAi_1.y = pointlist[i+1].y;
- result += (MAi.x*MAi_1.y - MAi_1.x*MAi.y);
- }
- MAi.x = pointlist[pointlist.size()-1].x;
- MAi.y = pointlist[pointlist.size()-1].y;
- MAi_1.x = pointlist[0].x;
- MAi_1.y = pointlist[0].y;
- result += (MAi.x*MAi_1.y - MAi_1.x*MAi.y);
- printf("%f\n",abs(result)/2.0);
- }
- 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]))
- 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]))
- 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]);
- Pirimier(a);
- Square(a);
- }
- int main()
- {
- int size(0);
- cin >> size;
- vector<pt> point;
- for (int i = 0; i < size; i++)
- {
- pt buf;
- cin >> buf.x;
- cin >> buf.y;
- point.push_back(buf);
- }
- convex_hull(point);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement