結果

問題 No.199 星を描こう
ユーザー hamrayhamray
提出日時 2021-09-15 19:26:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 20,062 bytes
コンパイル時間 2,682 ms
コンパイル使用メモリ 198,836 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-11 05:58:28
合計ジャッジ時間 4,175 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘bool intersect(const Line&, const Segment&)’ 内:
main.cpp:502:1: 警告: 非 void を戻す関数内に return 文がありません [-Wreturn-type]
  502 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
 
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
 
#define MOD 1000000007
 
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-8, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;
//ここから編集    
typedef string::const_iterator State;
ll GCD(ll a, ll b){
  return (b==0)?a:GCD(b, a%b);
}
ll LCM(ll a, ll b){
  return a/GCD(a, b) * b;
}
template< int mod >
struct ModInt {
  int x;
 
  ModInt() : x(0) {}
 
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
 
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
 
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
 
  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }
 
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
 
  ModInt operator-() const { return ModInt(-x); }
 
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
 
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
 
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
 
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
 
  bool operator==(const ModInt &p) const { return x == p.x; }
 
  bool operator!=(const ModInt &p) const { return x != p.x; }
 
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
 
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
 
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
 
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
 
  static int get_mod() { return mod; }
};
 
using modint = ModInt< 998244353 >;
template< typename T >
struct Combination {
  vector< T > _fact, _rfact, _inv;
 
  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }
 
  inline T fact(int k) const { return _fact[k]; }
 
  inline T rfact(int k) const { return _rfact[k]; }
 
  inline T inv(int k) const { return _inv[k]; }
 
  T P(int n, int r) const {
    if(r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }
 
  T C(int p, int q) const {
    if(q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }
 
  T H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
 
ll modpow(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  if(x == 0) return 0;
  while(n) {
    if(n&1) res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
} 
inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}
template<typename T> 
struct BIT{
  int N;
  std::vector<T> node;
  BIT(){}
  BIT(int n){
    N = n;
    node.resize(N+10);
  }
  void build(int n) {
    N = n;
    node.resize(N+10);
  }
  /* a: 1-indexed */
  void add(int a, T x){
    for(int i=a; i<(int)node.size(); i += i & -i) node[i] += x;
  }

  /* [1, a] */
  T sum(int a){
    T res = 0;
    for(int x=a; x>0; x -= x & -x) res += node[x];
    return res;
  }

  /* [l, r] */
  T rangesum(int l, int r){
    return sum(r) - sum(l-1);
  }

  /* 
    a1+a2+...+aw >= valとなるような最小のwを返す
    @verify https://codeforces.com/contest/992/problem/E
  */
  int lower_bound(T val) {
    if(val < 0) return 0;

    int res = 0;
    int n = 1; 
    while (n < N) n *= 2;

    T tv=0;
    for (int k = n; k > 0; k /= 2) {
      if(res + k < N && node[res + k] < val){
        val -= node[res+k];
        res += k;
      }
    }
    return res+1; 
  }
};
struct UnionFind{
  std::vector<int> par;
  std::vector<int> siz;

  UnionFind(int sz_): par(sz_), siz(sz_) {
    for(int i=0; i<sz_; ++i) par[i] = i, siz[i] = 1;
  }

  void init(int sz_){
    par.resize(sz_);
    siz.resize(sz_);
    for(int i=0; i<sz_; ++i) par[i] = i, siz[i] = 1;
  }

  int root(int x){
    if(x == par[x]) return x;
    return par[x] = root(par[x]);
  }

  bool merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return false;
    if(siz[x] < siz[y]) std::swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }

  bool issame(int x, int y){
    return root(x) == root(y);
  }

  int size(int x){
    return siz[root(x)];
  }
};
struct RollingHash{

    using ull = unsigned long long;
    const ull mod = (1ULL << 61) - 1;
    const ull MASK30 = (1ULL << 30) - 1;
    const ull MASK31 = (1ULL << 31) - 1;

    const ull MASK61 = mod;

    ull base;
    int n;
    vector<ull> hash, pow;

    RollingHash(const string &s)
    {
        random_device rnd;
        mt19937_64 mt(rnd());
        base = calc_mod(mt()) % 100000 + 1000;
        
        n = (int)s.size();
        hash.assign(n+1, 0);
        pow.assign(n+1, 1);
        
        for(int i=0; i<n; i++){
            hash[i+1] = calc_mod(mul(hash[i], base) + s[i]);
            pow[i+1] = calc_mod(mul(pow[i], base));
        }
    }

    ull calc_mod(ull x){
        ull xu = x >> 61;
        ull xd = x & MASK61;
        ull res = xu + xd;
        if(res >= mod) res -= mod;
        return res;
    }

    ull mul(ull a, ull b){
        ull au = a >> 31;
        ull ad = a & MASK31;
        ull bu = b >> 31;
        ull bd = b & MASK31;
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & MASK30;
        return calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd);
    }

    //[l,r)のハッシュ値
    inline ull get(int l, int r){
        ull res = calc_mod(hash[r] + mod*3-mul(hash[l], pow[r-l]));
        return res;
    }
    //string tのハッシュ値
    inline ull get(string t){
        ull res = 0;
        for(int i=0; i<t.size(); i++){
            res = calc_mod(mul(res, base)+t[i]);
        }
        return res;
    }
    //string s中のtの数をカウント
    inline int count(string t) {
        if(t.size() > n) return 0;
        auto hs = get(t);
        int res = 0;
        for(int i=0; i<n-t.size()+1; i++){
            if(get(i, i+t.size()) == hs) res++; 
        }
        return res;
    }

    /* 
        concat 
        @verify https://codeforces.com/problemset/problem/514/C
    */
    inline ull concat(ull h1, ull h2, int h2len){
      return calc_mod(h2 + mul(h1, pow[h2len]));
    }

    // LCPを求める S[a:] T[b:]
    inline int LCP(int a, int b){
        int len = min((int)hash.size()-a, (int)hash.size()-b);
        
        int lb = -1, ub = len;
        while(ub-lb>1){
            int mid = (lb+ub)/2;

            if(get(a, a+mid) == get(b, b+mid)) lb = mid;
            else ub = mid;
        }
        return lb;
    }
};
using Point = complex< double >;
bool eq(double a, double b){ return fabs(a-b) < EPS; }
namespace std {
  bool operator<(const Point a, const Point b) {
    if(eq(a.real(),b.real())) return a.imag() < b.imag();
    return a.real() < b.real();
  }
}

istream &operator>> (istream &is, Point &p) {
  double a, b;
  is >> a >> b;
  p = Point(a, b);
  return is;
}

ostream &operator<< (ostream &os, Point &p) {
  return os << fixed << setprecision(10) << p.real() << " " << p.imag();
}

bool operator<(const Point &a, const Point &b) {
  return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
}

// rotate Φ(rad)
// x = r * cos(θ + Φ)
//   = r * cos(θ) * cos(Φ) - r * sin(θ) * sin(Φ)
//   = x * cos(Φ) - y * sin(Φ) (∵ cos(θ) = x/r, sin(θ) = y/r)  
Point rotate(double phi, const Point &p) {
  double x = p.real(), y = p.imag();
  return Point(x * cos(phi) - y * sin(phi), x * sin(phi) + y * cos(phi));
}

double radian_to_degree(double r) {
  return (r * 180.0 / PI);
}

double degree_to_radian(double d) {
  return (d * PI / 180.0);
}

struct Line{
  Point a, b;

  Line() = default;

  Line(Point a, Point b) : a(a), b(b){}

  Line(double A, double B, double C){
    //ax + by = c
    if(eq(A, 0)){
      a = Point(0, C/B), b = Point(1, C/B);
    }else if(eq(B, 0)){
      a = Point(C/A, 0), b = Point(C/A, 1);
    }else{
      a = Point(0, C/B), b = Point(C/A, 0);
    }
  }

  friend istream &operator>>(istream &is, Line &a) {
    return is >> a.a >> a.b;
  }
  friend ostream &operator<<(ostream &os, Line &a) {
    return os << a.a << " to " << a.b;
  }
};

struct Segment: Line {
  Segment() = default;

  Segment(Point a, Point b) : Line(a, b) {}
};

struct Circle {
  Point p;
  double r;

  Circle() = default;

  Circle(Point p, double r): p(p), r(r){}
};

using Points = vector<Point>;
using Polygon = vector<Point>;
using Segments = vector<Segment>;
using Lines = vector<Line>;
using Circles = vector<Circle>;

double cross(const Point &a, const Point &b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

double dot(const Point& a, const Point &b) {
  return a.real() * b.real() + a.imag() * b.imag();
}

//https://mathtrain.jp/projection
Point projection(const Line &l, const Point &p){
  double t = dot(p - l.a, l.a-l.b) / norm(l.a - l.b);
  return l.a + (l.a - l.b) * t;
}

Point projection(const Segment &l, const Point &p){
  double t = dot(p - l.a, l.b-l.a) / norm(l.a - l.b);
  return l.a + (l.b - l.a) * t;
}

Point reflection(const Line &l, const Point &p){
  return p + (projection(l, p) - p) * 2.0;
}

int ccw(const Point &a, const Point &b, const Point &c) {
  if(cross(b-a, c-a) > EPS) return 1;   // "COUNTER_CLOCKWISE"
  if(cross(b-a, c-a) < -EPS) return -1; // "CLOCKWISE"
  if(dot(b-a, c-a) < -EPS) return 2;    // "ONLINE_BACK" c-a-b
  if(norm(b-a) < norm(c-a) - EPS) return -2;  // "ONLINE_FRONT" a-b-c
  return 0;                         // "ON_SEGMENT" a-c-b
}

bool parallel(const Line &a, const Line &b){
  return eq(cross(a.a-a.b, b.a-b.b), 0.0);
}
bool orthogonal(const Line &a, const Line &b){
  return eq(dot(a.a-a.b, b.a-b.b), 0.0);
}
enum { OUT, ON, IN };

int contains(const Polygon& Q, const Point& p){
  bool in = false;
  for(int i=0; i<Q.size(); i++){
    Point a = Q[i] - p, b = Q[(i+1)%Q.size()]-p;
    if(a.imag() > b.imag()) swap(a, b);
    if(a.imag() <= 0 && 0 < b.imag() && cross(a, b) < 0) in = !in;
    if(cross(a, b) == 0 && dot(a, b) <= 0) return ON;
  }
  return in ? IN : OUT;
}
bool intersect(const Segment &s, const Point &p){
  return ccw(s.a, s.b, p) == 0;
}

//直線の交差判定
bool intersect(const Line &a, const Line &b) {
  if(parallel(a, b)) return 0;
  return 1;
}

//線分が重なる/端点で交わるときtrue
bool intersect(const Segment &a, const Segment &b) {
  return ccw(a.a, a.b, b.a) * ccw(a.a, a.b, b.b) <= 0 && ccw(b.a, b.b, a.a) * ccw(b.a, b.b, a.b) <= 0;
}

bool intersect(const Line &l, const Segment &s) {
  
}

Point crosspoint(const Line &a, const Line &b){
  double d = cross(b.b-b.a, a.b-a.a);
  if(eq(d, 0.0)) return Point(1e9, 1e9); 
  
  return a.a + (a.b - a.a) * cross(b.b-b.a, b.b-a.a) / d;
}

Point crosspoint(const Segment &a, const Segment &b){
  return crosspoint(Line(a.a, a.b), Line(b.a, b.b));
}
double distance(const Point &a, const Point &b){
  return abs(a - b);
}
double distance(const Line &l, const Point &p){
  return abs( cross(p - l.a, l.b-l.a) / abs(l.b-l.a) );
}
double distance(const Segment &s, const Point &p){
  Point r = projection(s, p);
  if(intersect(s, r)) return abs(r-p);
  return min(abs(s.a - p), abs(s.b - p));
}
// double distance(const Line &a, const Line &b){

// }
// double distance(const Line &a, const Segment &b){

// }
double distance(const Segment &a, const Segment &b) {
  return intersect(a, b) ? 0 : min({distance(a, b.a), distance(a, b.b), distance(b, a.a), distance(b, a.b)});
}

/* 2円の交点 */
vector<Point> crosspointCC(Circle C1, Circle C2){
  vector<Point> ps;
  Point ab = C2.p - C1.p;
  double d = abs(ab);
  double rc = (C1.r * C1.r + d * d - C2.r * C2.r) / (2 * d);
  if(eq(d, 0) || C1.r < abs(rc)) return ps;

  double rs = sqrt(C1.r * C1.r - rc*rc);

  Point abN = ab * Point(0, rs/d);
  Point cp = C1.p + rc / d * ab;
  ps.push_back(cp + abN);
  if(!eq(norm(abN), 0))ps.push_back(cp-abN);
  return ps;
}

vector<Point> crosspointCL(Circle C, Line l){
  Point p = projection(l, C.p);

  Point e = (l.b-l.a)/abs(l.b-l.a);
  if(eq(distance(l, C.p), C.r)) {
    return vector<Point>{p, p};
  }
  double base = sqrt(C.r*C.r-norm(p-C.p));
  
  return vector<Point>{p+e*base, p-e*base};
}

/* 円同士の共通部分の面積を求める */
// verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_I date: 2020/10/11
long double AreaofCC(Circle& C1, Circle& C2){
  if(C1.r > C2.r) swap(C1, C2);
  long double nor = norm(C1.p - C2.p);
  long double dist = sqrtl(nor);
  
  if(C1.r + C2.r < dist+EPS) return 0;

  if(dist + C1.r < C2.r + EPS) return C1.r * C1.r * PI;

  long double theta1 = acosl((nor + C1.r*C1.r - C2.r * C2.r)/(2*C1.r*dist));

  long double theta2 = acosl((nor + C2.r*C2.r - C1.r * C1.r)/(2*C2.r*dist));
  
  return (theta1 - sinl(theta1+ theta1) *0.5) * C1.r * C1.r + (theta2 - sinl(theta2+theta2) *0.5) * C2.r * C2.r;
}


Polygon convex_hull(Polygon &p)
{
    int n = (int)p.size(), k = 0;
    if (n <= 2)
        return p;
    sort(p.begin(), p.end());
    vector<Point> ch(n * 2);

    for (int i = 0; i < n; ch[k++] = p[i++])
    {
        while (k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0)
            --k;
    }

    for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--])
    {
        while (k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0)
            --k;
    }
    ch.resize(k - 1);
    return ch;
}
double convex_diameter(const Polygon &p)
{
    int n = (int)p.size();
    if (n == 2)
        return abs(p[0] - p[1]);

    int is = 0, js = 0;
    for (int i = 1; i < n; ++i)
    {
        if (imag(p[i]) > imag(p[is]))
            is = i;
        if (imag(p[i]) < imag(p[js]))
            js = i;
    }

    double res = abs(p[is] - p[js]);
    int i, maxi, j, maxj;
    i = maxi = is;
    j = maxj = js;
    do
    {
        if (cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0)
            j = (j + 1) % n;
        else
            i = (i + 1) % n;
        res = max(res, abs(p[i] - p[j]));
    } while (i != is || j != js);
    return res;
}

Polygon convex_cut(const Polygon &p, const Line l)
{
    Polygon ret;
    for (int i = 0; i < p.size(); ++i)
    {
        Point now = p[i], nxt = p[(i + 1) % p.size()];
        if (ccw(l.a, l.b, now) != -1) //交点が線分l上にあるとき
            ret.push_back(now);
        if (ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0)
        {
            ret.push_back(crosspoint(Line(now, nxt), l));
        }
    }
    return (ret);
}
double closestpair(Points &a, int l, int r){
  if(r-l<=1) return 1e20;
  int mid = (l+r)/2;

  double X = a[mid].real();
  double d = min(closestpair(a, l, mid), closestpair(a, mid, r));
  inplace_merge(a.begin()+l, a.begin()+mid, a.begin()+r, [](const Point& pa, const Point& pb){
    return pa.imag() < pb.imag();
  });

  Points b;
  for(int i=l; i<r; i++){
    if(abs(a[i].real()-X) >= d) continue;
    for(int j=b.size()-1; j>=0; j--){
      if(abs((a[i]-b[j]).imag()) >= d) break;
      d = min(d, abs(a[i]-b[j]));
    }
    b.push_back(a[i]);
  }
  return d;
}

/* 円の交差判定 */
/* verify: http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=CGL date:2020/10/11 */
int intersectionCC(Circle c1, Circle c2){
  if(c1.r > c2.r) swap(c1, c2);
  double d1 = abs(c1.p-c2.p); 
  double d2 = c1.r + c2.r;
  if(d1 > d2) return 4; /* 互いに交点を持たない */
  else if(d1 == d2) return 3; /* 外接する場合 */
  else{
    if(c2.r == c1.r + d1) return 1; /* 内接する場合 */
    else if(c2.r > c1.r + d1) return 0; /* 包含 */
    else return 2; /* 交点を2つ持つ */
  }
}

/* 点集合が反時計回りに与えられる場合のみ */
double Area(Points &g){
  double res = 0;
  int n = g.size();
  REP(i,n){
    res += cross(g[i], g[(i+1)%n]);
  }
  return res/2.0;
}

/* 内接円 */
/* verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_B&lang=ja date: 2020/10/11 */
pair<Point, double> incircle_of_a_Triangle(Points &p){

  double a = abs(p[1]-p[2]), b = abs(p[2]-p[0]), c = abs(p[0]-p[1]);
  double s = (a+b+c) / 2.0;
  double S = sqrtl(s*(s-a)*(s-b)*(s-c));
  double r = S/s; 
  
  Point pp = (a*p[0]+b*p[1]+c*p[2])/(a+b+c);
  return make_pair(pp, r);
} 

/* 外接円 */
pair<Point, double> circumscribed_circle_of_a_triangle(Points &p){

  Point m1((p[0]+p[1])/2.0), m2((p[1]+p[2])/2.0);
  Point v((p[1]-p[0]).imag(), (p[0]-p[1]).real()), w((p[1]-p[2]).imag(), (p[2]-p[1]).real());

  Line l1(m1, Point(v+m1)), l2(m2, Point(w+m2));

  Point x = crosspoint(l1, l2);
  double r = abs(x-p[0]);
  return make_pair(x, r);
}

/* ある点pを通る円cの接線 */
Points tangent_to_a_circle(Point p, Circle C){
  Points ps;
  double d = abs(C.p-p);
  if(eq(d,0)){
    ps.push_back(p);
  }else if(d>EPS){
    
    double d2 = sqrt(d*d-C.r*C.r);
    
    long double theta = acosl(d2/d);
    //cout << theta << endl;
    Point pp = C.p - p;
    Point p2 = rotate(-theta, pp);

    Point e = p2/abs(p2);
    Point ppp = e*d2;
    ps.push_back(p + ppp);
    p2 = rotate(theta, pp);
    e = p2/abs(p2);
    ppp = e*d2;
    ps.push_back(p + ppp);
    
  }
  return ps;
}

Lines tangent(Circle C1, Circle C2){
  Lines ls;
  if(C1.r < C2.r) swap(C1, C2);
  double d = norm(C1.p - C2.p);
  if(eq(d, 0)) return ls;
  Point u = (C2.p - C1.p) / sqrt(d);
  Point v = rotate(pi/2, u);

  for(double s: {-1, 1}) {
    double h = (C1.r + s * C2.r) / sqrt(d);
    if(eq(1-h*h, 0)) {
      ls.emplace_back(C1.p + u * C1.r, C1.p + (u+v) * C1.r);
    }else if(1-h*h>0){
      Point uu = u*h, vv = v*sqrt(1-h*h);
      ls.emplace_back(C1.p + (uu+vv) * C1.r, C2.p - (uu+vv) * C2.r * s);
      ls.emplace_back(C1.p + (uu-vv) * C1.r, C2.p - (uu-vv) * C2.r * s);
    }
  }
  return ls;
}
Line bisector(Point a, Point b){
    Point A = (a+b)*Point(0.5, 0); 
    return Line(A, A+(b-a)*Point(0, PI/2));
}

Polygon voronoi_cell(Polygon Q, Points P, int s){
    REP(i,P.size()){
        if(i!=s){
            Q = convex_cut(Q, bisector(P[s], P[i]));
        }
    }
    return Q;
}
int main() {  
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  vector<pair<int, int>> vp(5);
  REP(i,5) cin >> vp[i].first >> vp[i].second;

  sort(all(vp), [&](auto& a, auto& b){
    double th0,th1;
    if(a.second == 0) th0 = 0;
    else th0 = atan2(a.second, a.first);
    if(b.second == 0) th1 = 0;
    else th1 = atan2(b.second, b.first);
    if(th0 < 0) th0 = 2*pi+th0;
    if(th1 < 0) th1 = 2*pi+th1;
    return th0 < th1;
  });
  Polygon poly(5);
  REP(i,5) poly[i] = Point(vp[i].first, vp[i].second);
  auto p = convex_hull(poly);
  if(p.size() == 5) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;

}
0