Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "iostream"
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- struct Coord{
- long long int x;
- long long int y;
- };
- struct DCoord{
- double x;
- double y;
- };
- Coord Po;
- int st = 100000;
- bool fun(Coord &a, Coord &b){
- if (((a.y - Po.y) * (b.x - Po.x)) < ((b.y - Po.y) * (a.x - Po.x))){
- return true;
- }
- if (((a.y - Po.y) * (b.x - Po.x)) == ((b.y - Po.y) * (a.x - Po.x))){
- 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))){
- return true;
- }
- }
- return false;
- }
- bool check_left(Coord a, Coord b, Coord c){
- Coord u = {b.x - a.x, b.y - a.y};
- Coord v = {c.x - b.x, c.y - b.y};
- if ((u.x * v.y - u.y * v.x) >= 0){
- return true;
- }
- return false;
- }
- vector <Coord> graham(vector<Coord> dots){
- Po = dots[0];
- for (int i = 1; i < dots.size(); i++){
- if (dots[i].y < Po.y){
- Po = dots[i];
- }
- else if (Po.y == dots[i].y){
- if (dots[i].x < Po.x){
- Po = dots[i];
- }
- }
- }
- sort(dots.begin(), dots.end(), fun);
- vector<Coord> res;
- res.push_back(dots[0]);
- res.push_back(dots[1]);
- for (int i = 2; i < dots.size(); i++){
- while(!check_left(res[res.size()-2],res[res.size()-1],dots[i])){
- res.pop_back();
- }
- res.push_back(dots[i]);
- }
- return res;
- }
- double fence_length(vector<Coord> arrr){
- vector <DCoord> arr;
- float dx;
- float dy;
- for (int i = 0; i < arrr.size(); i++){
- dx = arrr[i].x / double(st);
- dy = arrr[i].y / double(st);
- arr.push_back({dx, dy});
- }
- 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));
- for (int i=0; i<arr.size()-1; i++){
- 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));
- }
- return res;
- }
- int main(){
- vector <Coord> dots;
- ifstream inf;
- inf.open("input.txt");
- int n;
- inf >> n;
- float dx;
- float dy;
- for (int i = 0; i < n; i++) {
- inf >> dx >> dy;
- dots.push_back({int(dx*st), int(dy*st)});
- }
- inf.close();
- ofstream outf;
- outf.open("output.txt");
- outf << fixed;
- outf.precision(5);
- outf << fence_length(graham(dots));
- outf.close();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement