Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <functional>
- #include <algorithm>
- #include <math.h>
- #include <queue>
- using namespace std;
- struct point {
- int x;
- int y;
- };
- point P1;
- int iloczyn(point a, point b, point c) {
- int pole = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
- if (pole > 0)
- return -1;
- else if (pole < 0)
- return 1;
- return 0;
- }
- int dist(point a, point b) {
- int dx = a.x - b.x, dy = a.y - b.y;
- return dx*dx + dy*dy;
- }
- bool comp(point a, point b){
- int order = iloczyn(a, b, P1);
- if (order == 0)
- return !(dist(P1, a) < dist(P1, b));
- return !(order == -1);
- }
- int main() {
- P1.x = 500000;
- P1.y = 500000;
- int n; scanf("%d", &n);
- point *tab = new point[n-1];
- int x, y; scanf("%d %d", &x, &y); P1.x = x; P1.y = y;
- //////////////////////////////////////
- for (int i = 0; i < n-1; i++) {
- scanf("%d %d", &x, &y);
- tab[i].x = x; tab[i].y = y;
- if (tab[i].x < P1.x || (tab[i].x == P1.x && tab[i].y < P1.y)) {
- swap(P1, tab[i]);
- }
- }
- sort(tab, tab + n-1, comp);
- vector<point> otoczka;
- otoczka.push_back(tab[0]);
- otoczka.push_back(tab[1]);
- otoczka.push_back(tab[2]);
- for (int i = 3; i < n - 1; i++) {
- point top = otoczka.back();
- otoczka.pop_back();
- while (iloczyn(otoczka.back(), top, tab[i]) == -1) {
- top = otoczka.back();
- otoczka.pop_back();
- }
- otoczka.push_back(top);
- otoczka.push_back(tab[i]);
- }
- //////////////////////////////////////
- printf("%c", 'X');
- return 0;
- }
- //@author Tooster
- /*
- 5
- 1 1
- 1 2
- 2 3
- 3 2
- 2 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement