Advertisement
Maskalor

Untitled

Mar 19th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. #include "iostream"
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <fstream>
  6.  
  7. using namespace std;
  8.  
  9. struct Coord{
  10.     long long int x;
  11.     long long int y;
  12. };
  13.  
  14. struct DCoord{
  15.     double x;
  16.     double y;
  17. };
  18.  
  19. Coord Po;
  20. int st = 100000;
  21.  
  22. bool fun(Coord &a, Coord &b){    
  23.     if (((a.y - Po.y) * (b.x - Po.x)) < ((b.y - Po.y) * (a.x - Po.x))){
  24.         return true;
  25.     }
  26.     if (((a.y - Po.y) * (b.x - Po.x)) == ((b.y - Po.y) * (a.x - Po.x))){
  27.         if (sqrt((a.x - Po.x) * (a.x - Po.x) + (a.y - Po.y) * (a.y - Po.y)) < sqrt((b.x - Po.x) * (b.x - Po.x) + (b.y - Po.y) * (b.y - Po.y))){
  28.             return true;
  29.         }
  30.  
  31.     }
  32.     return false;
  33. }
  34.  
  35. bool check_left(Coord a, Coord b, Coord c){
  36.     Coord u = {b.x - a.x, b.y - a.y};
  37.     Coord v = {c.x - b.x, c.y - b.y};
  38.     if ((u.x * v.y - u.y * v.x) >= 0){
  39.         return true;
  40.     }
  41.     return false;
  42. }
  43.  
  44. vector <Coord> graham(vector<Coord> dots){
  45.     Po = dots[0];
  46.     for (int i = 1; i < dots.size(); i++){
  47.         if (dots[i].y < Po.y){
  48.             Po = dots[i];
  49.         }
  50.         else if (Po.y == dots[i].y){
  51.             if (dots[i].x < Po.x){
  52.                 Po = dots[i];
  53.             }
  54.         }
  55.     }
  56.     sort(dots.begin(), dots.end(), fun);
  57.  
  58.     vector<Coord> res;
  59.     res.push_back(dots[0]);
  60.     res.push_back(dots[1]);
  61.     for (int i = 2; i < dots.size(); i++){
  62.         while(!check_left(res[res.size()-2],res[res.size()-1],dots[i])){
  63.             res.pop_back();
  64.         }
  65.         res.push_back(dots[i]);
  66.     }
  67.     return res;
  68. }
  69.  
  70. double fence_length(vector<Coord> arrr){
  71.     vector <DCoord> arr;
  72.     float dx;
  73.     float dy;
  74.     for (int i = 0; i < arrr.size(); i++){
  75.         dx = arrr[i].x / double(st);
  76.         dy = arrr[i].y / double(st);
  77.         arr.push_back({dx, dy});
  78.     }
  79.    
  80.     double res = sqrt((arr[0].x - arr[arr.size()-1].x) * (arr[0].x - arr[arr.size()-1].x) + (arr[0].y - arr[arr.size()-1].y) * (arr[0].y - arr[arr.size()-1].y));
  81.     for (int i=0; i<arr.size()-1; i++){
  82.         res += sqrt((arr[i+1].x - arr[i].x) * (arr[i+1].x - arr[i].x) + (arr[i+1].y - arr[i].y) * (arr[i+1].y - arr[i].y));
  83.     }
  84.     return res;
  85. }
  86.  
  87.  
  88. int main(){
  89.     vector <Coord> dots;
  90.  
  91.     ifstream inf;
  92.     inf.open("input.txt");
  93.  
  94.     int n;
  95.     inf >> n;
  96.     float dx;
  97.     float dy;
  98.     for (int i = 0; i < n; i++) {
  99.         inf >> dx >> dy;
  100.         dots.push_back({int(dx*st), int(dy*st)});
  101.     }
  102.     inf.close();
  103.  
  104.     ofstream outf;
  105.     outf.open("output.txt");
  106.     outf << fixed;
  107.     outf.precision(5);
  108.     outf << fence_length(graham(dots));
  109.     outf.close();
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement