Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <cassert>
- #define N 1005
- using namespace std;
- struct vect {
- int x, y;
- void read() {
- cin >> x >> y;
- }
- void print() {
- cout << x << " " << y << endl;
- }
- vect() {}
- vect(int a, int b) {
- x = a, y = b;
- }
- int sq_length() {
- return x * x + y * y;
- }
- };
- vect operator - (vect a, vect b) {
- return vect(a.x - b.x, a.y - b.y);
- }
- int operator * (vect a, vect b) {
- return a.x * b.y - a.y * b.x;
- }
- int operator ^ (vect a, vect b) {
- return a.x * b.x + a.y * b.y;
- }
- vect start, center, p[N], p2[N], st[N];
- int n, top = 0, m;
- bool del[N];
- void push(vect a) {
- st[top++] = a;
- }
- bool comp(vect a, vect b) {
- a = a - start;
- b = b - start;
- if (a * b == 0)
- return a.sq_length() < b.sq_length();
- return a * b > 0;
- }
- int main() {
- cin >> n;
- center.read();
- for (int i = 0; i < n; i++)
- p[i].read();
- start = p[0];
- int ind = 0;
- for (int i = 1; i < n; i++)
- if (p[i].y < start.y || (p[i].y == start.y && p[i].x < start.x))
- start = p[i], ind = i;
- swap(p[0], p[ind]);
- sort(p + 1, p + n, comp);
- for (int i = n - 2; i > 0; i--)
- if ( (p[i] - start) * (p[i + 1] - start) == 0 )
- del[i] = true;
- for (int i = 0; i < n; i++)
- if (!del[i])
- p2[m++] = p[i];
- p2[m++] = p2[0];
- for (int i = 0; i < 3; i++)
- push(p2[i]);
- for (int i = 3; i < m; i++) {
- while ((p2[i] - st[top - 1]) * (st[top - 1] - st[top - 2]) >= 0)
- top--;
- push(p2[i]);
- }
- int answer = 0;
- for (int i = 1; i < top; i++) {
- if ( ((center - st[i - 1]) ^ (st[i] - st[i - 1])) > 0 && ((center - st[i]) ^ (st[i - 1] - st[i])) > 0 )
- answer++;
- }
- cout << answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement