Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- using namespace std;
- #define eps 1e-9
- #define eq(a, b) (abs(a - b) < eps)
- #define lt(a, b) (a < b - eps)
- #define gt(a, b) (a > b + eps)
- #define le(a, b) (a < b + eps)
- #define ge(a, b) (a > b - eps)
- #define ftype float
- const ftype PI = acos(-1.0);
- // Begin Point 2D
- struct point2d {
- ftype x, y;
- point2d() : x(0.0), y(0.0) {}
- point2d(const ftype& x, const ftype& y) : x(x), y(y) {}
- point2d& operator=(const point2d& oth) {
- x = oth.x; y = oth.y;
- return (*this);
- }
- point2d& operator+=(const point2d& oth) {
- x += oth.x; y += oth.y;
- return (*this);
- }
- point2d& operator-=(const point2d& oth) {
- x -= oth.x; y -= oth.y;
- return (*this);
- }
- point2d& operator*=(const ftype& factor) {
- x *= factor; y *= factor;
- return (*this);
- }
- point2d& operator/=(const ftype& factor) {
- x /= factor; y /= factor;
- return (*this);
- }
- };
- point2d operator+(const point2d& a, const point2d& b) {
- return point2d(a.x + b.x, a.y + b.y);
- }
- point2d operator-(const point2d& a, const point2d& b) {
- return point2d(a.x - b.x, a.y - b.y);
- }
- point2d operator*(const point2d& a, const ftype& factor) {
- return point2d(a.x * factor, a.y * factor);
- }
- point2d operator*(const ftype& factor, const point2d& a) {
- return point2d(factor * a.x, factor * a.y);
- }
- point2d operator/(const point2d& a, const ftype& factor) {
- return point2d(a.x / factor, a.y / factor);
- }
- bool operator==(const point2d& a, const point2d& b) {
- return (eq(a.x, b.x) and eq(a.y, b.y));
- }
- bool operator!=(const point2d& a, const point2d& b) {
- return !(a==b);
- }
- bool operator < (const point2d& a, const point2d& b) {
- return (lt(a.x, b.x) or (eq(a.x, b.x) and lt(a.y, b.y)));
- }
- bool operator > (const point2d& a, const point2d& b) {
- return (b < a);
- }
- bool operator <= (const point2d& a, const point2d& b) {
- return !(a > b);
- }
- bool operator >= (const point2d& a, const point2d& b) {
- return !(a < b);
- }
- // > 0 if |angle| < pi/2
- // = 0 if |angle| = pi
- // < 0 if |angle| > pi/2
- ftype operator*(const point2d& a, const point2d& b) {
- return (a.x * b.x + a.y * b.y);
- }
- // < 0 if a comes before b in ccw
- // = 0 if a is collinear to b
- // > 0 if a comes after b in ccw
- ftype operator^(const point2d& a, const point2d& b) {
- return (a.x * b.y - a.y * b.x);
- }
- ftype ccw(const point2d& a, const point2d& b) {
- return (a ^ b);
- }
- // ccw(a, b, c) : > 0 if a comes before b counterclockwise in origin
- // ccw(a, b, c) : < 0 if a comes after b counterclockwise in origin
- ftype ccw(const point2d& a, const point2d& b, const point2d& origin) {
- return ccw(a - origin, b - origin);
- }
- ftype abs(const point2d& a) {
- return (a * a);
- }
- ftype norm(const point2d& a) {
- return sqrt(abs(a));
- }
- ftype dist(const point2d& a, const point2d& b) {
- return norm(a - b);
- }
- // Left rotation. Angle (rad)
- point2d rotate(const point2d& a, const ftype& angleSin, const ftype& angleCos) {
- return point2d(a.x * angleCos - a.y * angleSin, a.x * angleSin + a.y * angleCos);
- }
- point2d rotate(const point2d& a, const ftype& angle) {
- return rotate(a, sin(angle), cos(angle));
- }
- // 0 to 1 and 2 quadrant. 1 to 3 and 4
- int half(const point2d& p) {
- if (gt(p.y, 0) or (eq(p.y, 0) and ge(p.x, 0))) return 0;
- return 1;
- }
- // angle(a) < angle(b)
- bool cmpByAngle(const point2d& a, const point2d& b) {
- int ha = half(a), hb = half(b);
- if (ha != hb) return ha < hb;
- ftype c = a^b;
- if (eq(c, 0)) return lt(norm(a), norm(b));
- return gt(c, 0);
- }
- // End Point 2D
- const ftype angleBase = PI/4.0;
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- int n; cin >> n;
- vector<point2d> pts(n);
- for (int i = 0; i < n; ++i) {
- cin >> pts[i].x >> pts[i].y;
- }
- sort(pts.begin(), pts.end(), cmpByAngle);
- int ans = 0, r = 0;
- for (int i = 0; i < n; ++i) {
- point2d rotated = rotate(pts[i], angleBase);
- while (r < n and cmpByAngle(pts[r], rotated)) {
- ++r;
- }
- ans = max(ans, r - i);
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement