Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <string>
- #include <cmath>
- #include <iostream>
- using namespace std;
- struct Point{
- double x;
- double y;
- };
- double scalar_product(Point p1, Point p2){
- return p1.x * p2.y - p2.x * p1.y;
- }
- double length(Point p1, Point p2){
- return std::hypot(p1.x - p2.x, p1.y - p2.y);
- }
- double angle(Point p1, Point p2, Point p3){
- Point v1 = {p1.x - p2.x, p1.y - p2.y};
- Point v2 = {p3.x - p2.x, p3.y - p2.y};
- return acos((scalar_product(v1, v2))/(length(p1, p2) * length(p2, p3)));
- }
- double polar_angle(Point p1, Point p2){
- return angle({-abs(p1.x) - 1, p1.x}, p1, p2);
- }
- int main() {
- int n;
- cin >> n;
- vector<Point> coords(n);
- Point start = {1e5, 1e5};
- int cur_v;
- for (int i = 0; i < n; ++i){
- double x, y;
- cin >> x >> y;
- coords[i] = {x, y};
- if (start.y > coords[i].y || start.y == coords[i].y && start.x > coords[i].x){
- start = coords[i];
- cur_v = i;
- }
- }
- vector<int> convex_hull = {cur_v};
- Point mn = coords[cur_v];
- coords.erase(coords.begin() + cur_v);
- sort(coords.begin(), coords.end(), [&](const Point& a, const Point& b){ return polar_angle(start, a) < polar_angle(start, b);});
- double max_diff = 0;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement