#include<bits/stdc++.h>
using namespace std;
typedef complex < double > P;
typedef vector< P > G;
vector< G > g;
const double EPS = 1e-8;
const double INF = 1e12;
double cross(const P& a,const P& b){ //??????
  return imag(conj(a) * b);
}
double dot(const P& a,const P& b){ // ??????
  return real(conj(a) * b);
}
struct L: vector < P >{
  L(const P& a,const P& b){
    push_back(a);
    push_back(b);
  }
};
int ccw(P a,P b,P c){
  b -= a; c -= a;
  if(cross(b,c) > 0) return 1;
  if(cross(b,c) < 0) return -1;
  if(dot(b,c) < 0) return 2; // c--a--b
  if(norm(b) < norm(c)) return -2; // a--b--c
  return 0; // a--c--b
}
bool intersectSS(const L& s,const L& t){ //???????????? ??????:??????
  return ccw(s[0],s[1],t[0]) * ccw(s[0],s[1],t[1]) <= 0 &&
    ccw(t[0],t[1],s[0]) * ccw(t[0],t[1],s[1]) <= 0;
}
#define curr(P,i) P