namespace Geometry {
using T = ll;
constexpr T eps = 0;
bool eq(const T &x, const T &y) { return abs(x - y) <= eps; }
inline constexpr int type(T x, T y) {
if(x == 0 and y == 0) return 0;
if(y < 0 or (y == 0 and x > 0)) return -1;
return 1;
}
struct Point {
T x, y;
constexpr Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}
constexpr Point operator+() const noexcept { return *this; }
constexpr Point operator-() const noexcept { return Point(-x, -y); }
constexpr Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
constexpr Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
constexpr Point &operator+=(const Point &p) { return x += p.x, y += p.y, *this; }
constexpr Point &operator-=(const Point &p) { return x -= p.x, y -= p.y, *this; }
constexpr T operator*(const Point &p) const { return x * p.x + y * p.y; }
constexpr Point &operator*=(const T &k) { return x *= k, y *= k, *this; }
constexpr Point operator*(const T &k) { return Point(x * k, y * k); }
constexpr bool operator==(const Point &r) const noexcept { return r.x == x and r.y == y; }
constexpr T cross(const Point &r) const { return x * r.y - y * r.x; }
constexpr bool operator<(const Point &r) const { return pair(x, y) < pair(r.x, r.y); }
// 1 : left, 0 : same, -1 : right
constexpr int toleft(const Point &r) const {
auto t = cross(r);
return t > eps ? 1 : t < -eps ? -1 : 0;
}
constexpr bool arg_cmp(const Point &r) const {
int L = type(x, y), R = type(r.x, r.y);
if(L != R) return L < R;
T X = x * r.y, Y = r.x * y;
if(X != Y) return X > Y;
return x < r.x;
}
};
bool arg_cmp(const Point &l, const Point &r) { return l.arg_cmp(r); }
ostream &operator<<(ostream &os, const Point &p) { return os << p.x << " " << p.y; }
istream &operator>>(istream &is, Point &p) {
is >> p.x >> p.y;
return is;
}
struct Line {
Point a, b;
Line() = default;
Line(Point a, Point b) : a(a), b(b) {}
// ax + by = c
Line(T A, T B, T C) {
if(A == 0) {
a = Point(0, C / B), b = Point(1, C / B);
} else if(B == 0) {
a = Point(C / A, 0), b = Point(C / A, 1);
} else {
a = Point(0, C / B), b = Point(C / A, 0);
}
}
// 1 : left, 0 : same, -1 : right
constexpr int toleft(const Point &r) const {
auto t = (b - a).cross(r - a);
return t > eps ? 1 : t < -eps ? -1 : 0;
}
friend std::ostream &operator<<(std::ostream &os, Line &ls) {
return os << "{"
<< "(" << ls.a.x << ", " << ls.a.y << "), (" << ls.b.x << ", " << ls.b.y << ")}";
}
};
istream &operator>>(istream &is, Line &p) { return is >> p.a >> p.b; }
struct Segment : Line {
Segment() = default;
Segment(Point a, Point b) : Line(a, b) {}
};
ostream &operator<<(ostream &os, Segment &p) { return os << p.a << " to " << p.b; }
istream &operator>>(istream &is, Segment &p) {
is >> p.a >> p.b;
return is;
}
struct Circle {
Point p;
T r;
Circle() = default;
Circle(Point p, T r) : p(p), r(r) {}
};
using pt = Point;
using Points = vector<pt>;
using Polygon = Points;
T cross(const pt &x, const pt &y) { return x.x * y.y - x.y * y.x; }
T dot(const pt &x, const pt &y) { return x.x * y.x + x.y * y.y; }
T abs2(const pt &x) { return dot(x, x); }
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
// 点の回転方向
int ccw(const Point &a, Point b, Point c) {
b = b - a, c = c - a;
if(cross(b, c) > 0) return +1; // "COUNTER_CLOCKWISE"
if(cross(b, c) < 0) return -1; // "CLOCKWISE"
if(dot(b, c) < 0) return +2; // "ONLINE_BACK"
if(abs2(b) < abs2(c)) return -2; // "ONLINE_FRONT"
return 0; // "ON_SEGMENT"
}
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
// 平行判定
bool parallel(const Line &a, const Line &b) { return (cross(a.b - a.a, b.b - b.a) == 0); }
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
// 垂直判定
bool orthogonal(const Line &a, const Line &b) { return (dot(a.a - a.b, b.a - b.b) == 0); }
bool intersect(const Line &l, const Point &p) { return abs(ccw(l.a, l.b, p)) != 1; }
bool intersect(const Line &l, const Line &m) { return !parallel(l, m); }
bool intersect(const Segment &s, const Point &p) { return ccw(s.a, s.b, p) == 0; }
bool intersect(const Line &l, const Segment &s) { return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) <= 0; }
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
bool intersect(const Segment &s, const Segment &t) { return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0; }
bool intersect(const Polygon &ps, const Polygon &qs) {
int pl = si(ps), ql = si(qs), i = 0, j = 0;
while((i < pl or j < ql) and (i < 2 * pl) and (j < 2 * ql)) {
auto ps0 = ps[(i + pl - 1) % pl], ps1 = ps[i % pl];
auto qs0 = qs[(j + ql - 1) % ql], qs1 = qs[j % ql];
if(intersect(Segment(ps0, ps1), Segment(qs0, qs1))) return true;
Point a = ps1 - ps0;
Point b = qs1 - qs0;
T v = cross(a, b);
T va = cross(qs1 - qs0, ps1 - qs0);
T vb = cross(ps1 - ps0, qs1 - ps0);
if(!v and va < 0 and vb < 0) return false;
if(!v and !va and !vb) {
i += 1;
} else if(v >= 0) {
if(vb > 0)
i += 1;
else
j += 1;
} else {
if(va > 0)
j += 1;
else
i += 1;
}
}
return false;
}
T norm(const Point &p) { return p.x * p.x + p.y * p.y; }
Point projection(const Segment &l, const Point &p) {
T t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + (l.a - l.b) * t;
}
Point crosspoint(const Line &l, const Line &m) {
T A = cross(l.b - l.a, m.b - m.a);
T B = cross(l.b - l.a, l.b - m.a);
if(A == 0 and B == 0) return m.a;
return m.a + (m.b - m.a) * (B / A);
}
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C
Point crosspoint(const Segment &l, const Segment &m) { return crosspoint(Line(l), Line(m)); }
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B
// 凸性判定
bool is_convex(const Points &p) {
int n = (int)p.size();
for(int i = 0; i < n; i++) {
if(ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
}
return true;
}
Points convex_hull(Points p) {
int n = p.size(), k = 0;
if(n <= 2) return p;
sort(begin(p), end(p), [](pt x, pt y) { return (x.x != y.x ? x.x < y.x : x.y < y.y); });
Points ch(2 * n);
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;
}
// 面積の 2 倍
T area2(const Points &p) {
T res = 0;
rep(i, si(p)) { res += cross(p[i], p[i == si(p) - 1 ? 0 : i + 1]); }
return res;
}
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.y > b.y) swap(a, b);
if(a.y <= 0 && 0 < b.y && cross(a, b) < 0) in = !in;
if(cross(a, b) == 0 && dot(a, b) <= 0) return _ON;
}
return in ? _IN : _OUT;
}
Polygon Minkowski_sum(const Polygon &P, const Polygon &Q) {
vector<Segment> e1(P.size()), e2(Q.size()), ed(P.size() + Q.size());
const auto cmp = [](const Segment &u, const Segment &v) { return (u.b - u.a).arg_cmp(v.b - v.a); };
rep(i, P.size()) e1[i] = {P[i], P[(i + 1) % P.size()]};
rep(i, Q.size()) e2[i] = {Q[i], Q[(i + 1) % Q.size()]};
rotate(begin(e1), min_element(all(e1), cmp), end(e1));
rotate(begin(e2), min_element(all(e2), cmp), end(e2));
merge(all(e1), all(e2), begin(ed), cmp);
const auto check = [](const Points &res, const Point &u) {
const auto back1 = res.back(), back2 = *prev(end(res), 2);
return eq(cross(back1 - back2, u - back2), eps) and dot(back1 - back2, u - back1) >= -eps;
};
auto u = e1[0].a + e2[0].a;
Points res{u};
res.reserve(P.size() + Q.size());
for(const auto &v : ed) {
u = u + v.b - v.a;
while(si(res) >= 2 and check(res, u)) res.pop_back();
res.eb(u);
}
if(res.size() and check(res, res[0])) res.pop_back();
return res;
}
// -1 : on, 0 : out, 1 : in
// O(log(n))
int is_in(const Polygon &p, const Point &a) {
if(p.size() == 1) return a == p[0] ? -1 : 0;
if(p.size() == 2) return intersect(Segment(p[0], p[1]), a);
if(a == p[0]) return -1;
if((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1) return 0;
const auto cmp = [&](const Point &u, const Point &v) { return (u - p[0]).toleft(v - p[0]) == 1; };
const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
if(i == 1) return intersect(Segment(p[0], p[i]), a) ? -1 : 0;
if(i == p.size() - 1 && intersect(Segment(p[0], p[i]), a)) return -1;
if(intersect(Segment(p[i - 1], p[i]), a)) return -1;
return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;
}
Points halfplane_intersection(vector<Line> L, const T inf = 1e9) {
Point box[4] = {Point(inf, inf), Point(-inf, inf), Point(-inf, -inf), Point(inf, -inf)};
rep(i, 4) { L.emplace_back(box[i], box[(i + 1) % 4]); }
sort(all(L), [](const Line &l, const Line &r) { return (l.b - l.a).arg_cmp(r.b - r.a); });
deque<Line> dq;
int len = 0;
auto check = [](const Line &a, const Line &b, const Line &c) { return a.toleft(crosspoint(b, c)) == -1; };
rep(i, L.size()) {
while(dq.size() > 1 and check(L[i], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();
while(dq.size() > 1 and check(L[i], dq[0], dq[1])) dq.pop_front();
// dump(L[i], si(dq));
if(dq.size() and eq(cross(L[i].b - L[i].a, dq.back().b - dq.back().a), 0)) {
if(dot(L[i].b - L[i].a, dq.back().b - dq.back().a) < eps) return {};
if(L[i].toleft(dq.back().a) == -1)
dq.pop_back();
else
continue;
}
dq.emplace_back(L[i]);
}
while(dq.size() > 2 and check(dq[0], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();
while(dq.size() > 2 and check(dq.back(), dq[0], dq[1])) dq.pop_front();
if(si(dq) < 3) return {};
Polygon ret(dq.size());
rep(i, dq.size()) ret[i] = crosspoint(dq[i], dq[(i + 1) % dq.size()]);
return ret;
}
} // namespace Geometry
using namespace Geometry;#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // 包含所有容器(哈希表、树、堆)
#include <ext/pb_ds/tree_policy.hpp> // 包含树的相关策略(用于实现平衡树)
#include <ext/pb_ds/hash_policy.hpp> // 包含哈希表的相关策略
//#include <ext/pb_ds/priority_queue.hpp> // 包含优先级队列(堆)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define up(i, a, b) for (int i = (a); i <= (b); ++i)
#define down(i, a, b) for (int i = (a); i >= (b); --i)
#define sm int,vector<int>,greater<int>
#define int long long
mt19937_64 gen(12345);
const int N=1e6+5,mod=998244353,inf=1e9+7;;
int n,m,q,k;
int a[N],b[N],c[N],d[N];
int gcd(int x,int y)
{
if(y==0)return x;
return gcd(y,x%y);
}
int ksm(int a,int n,int p)
{
if(n<0)return 0;
int res=1;
while(n)
{
if(n&1)res=res*a%p;
n>>=1;
a=a*a%p;
}
return res;
}
const double eps = 1e-9;
int sgn(double x) {
if (abs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator - (const Point& b) const {
return Point(x - b.x, y - b.y);
}
//优先按 x 排序,x 相同按 y 排序
bool operator < (const Point& b) const {
if (sgn(x - b.x) == 0) return sgn(y - b.y) < 0;
return sgn(x - b.x) < 0;
}
// 判等(用于去重)
bool operator == (const Point& b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
};
double cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
// 返回值 > 0:p2 在 p0->p1 的左侧(向左转)
// 返回值 < 0:p2 在 p0->p1 的右侧(向右转)
// 返回值 == 0:三点共线
double cross(const Point& p0, const Point& p1, const Point& p2) {
return cross(p1 - p0, p2 - p0);
}
int dist(const Point& p0, const Point& p1){
return (p0.x-p1.x)*(p0.x-p1.x)+(p0.y-p1.y)*(p0.y-p1.y);
}
// 输入点集 P,返回凸包上的点集(逆时针顺序,起点和终点不重合)
vector<Point> convex_hull(vector<Point>& P) {
int n = P.size();
if (n <= 2) return P; // 退化情况:点数小于等于2,本身就是凸包
// 1. 排序并去重
sort(P.begin(), P.end());
P.erase(unique(P.begin(), P.end()), P.end());
n = P.size();
if (n <= 2) return P;
vector<Point> hull(2 * n); // 用数组模拟栈,速度最快
int top = 0; // 栈顶指针,表示栈内元素个数
// 2. 求下凸壳
for (int i = 0; i < n; i++) {
// 【核心判断】:如果向右转或共线,则弹栈
// 注意:如果你需要保留凸包边上的共线点,把 <= 改成 < 即可
while (top >= 2 && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {
top--;
}
hull[top++] = P[i];
}
// 3. 求上凸壳
int tmp = top; // 记录下凸壳的元素个数,上凸壳弹栈时不能破坏下凸壳
for (int i = n - 2; i >= 0; i--) {
while (top > tmp && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {
top--;
}
hull[top++] = P[i];
}
if (n > 1) top--;
hull.resize(top);
return hull;
}
int hull_diam(vector<Point>& hull){
int j=2;
int ans=0,H=hull.size();
if (H == 2) {
return dist(hull[0], hull[1]) ;
}
if (H <= 1) {
return 0;
}
up(i,0,H-1){
int next_i=(i+1)%H;
while(cross(hull[i],hull[next_i],hull[j])<=cross(hull[i],hull[next_i],hull[(j+1)%H])){
j=(j+1)%H;
}
ans=max(ans,dist(hull[i],hull[j]));
ans=max(ans,dist(hull[next_i],hull[j]));
}
return ans;
}
void solve(){
cin>>n;
vector<Point>pts(n);
up(i,0,n-1)cin>>pts[i].x>>pts[i].y;
vector<Point>hull=convex_hull(pts);
cout<<hull_diam(hull);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--){
solve();
}
// system("x-www-browser https://ys.mihoyo.com/");
// cout << fixed << setprecision(10) << x << '\n';
return 0;
}
/*
1
38133 49107
2 27269
*/#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define Re register LD
#define abs(x) (x<0?-x:x)
#define sakura(x) (x<0?'-':'+')
using namespace std;
struct Poi{LD x,y;inline void CL(){x=y=0;}}a1,a2,a3,xin;
struct Line{
LD k,b;
inline void CL(){k=b=0;}
inline void calc(Poi a,Poi c){k=(a.y-c.y)/(a.x-c.x),b=a.y-k*a.x;}// 由两点确定一条直线
inline void calc_(Poi a,Re K){k=K,b=a.y-k*a.x;}
}L1,L2,L3,L4;
inline Poi Get_half(Poi a,Poi b){// 求两圆交点
Poi c;
c.x=(a.x+b.x)/2.0,c.y=(a.y+b.y)/2.0;
return c;
}
inline Poi Get_LPL(Line a,Line b){
Poi c;
c.x=(b.b-a.b)/(a.k-b.k),c.y=a.k*c.x+a.b;
return c;
}
inline LD S(Re a){return a*a;}
inline LD Get_dis(Poi a,Poi b){// 撤销操作�
return sqrt(S(a.x-b.x)+S(a.y-b.y));
}
LD R;
int main(){
// freopen("123.txt","r",stdin);
while(scanf("%lf%lf%lf%lf%lf%lf",&a1.x,&a1.y,&a2.x,&a2.y,&a3.x,&a3.y)!=EOF){
xin.CL(),L1.CL(),L2.CL(),L3.CL(),L4.CL();
L1.calc(a1,a2),L2.calc(a2,a3);
L3.calc_(Get_half(a1,a2),-1.0/L1.k);
L4.calc_(Get_half(a2,a3),-1.0/L2.k);
xin=Get_LPL(L3,L4);
R=Get_dis(xin,a1);
Re a=-xin.x,b=-xin.y,c=R,d=-2.0*xin.x,e=-2.0*xin.y,f=S(xin.x)+S(xin.y)-S(R);
if(a!=0)printf("(x %c %.3lf)^2 ",sakura(a),abs(a));
else printf("x^2 ");
if(b!=0)printf("+ (y %c %.3lf)^2 ",sakura(b),abs(b));
else printf("+ y^2 ");
printf("= %.3lf^2\n",c);
printf("x^2 + y^2");
if(d!=0)printf(" %c %.3lf%c",sakura(d),abs(d),'x');
if(e!=0)printf(" %c %.3lf%c",sakura(e),abs(e),'y');
if(f!=0)printf(" %c %.3lf%c",sakura(f),abs(f),' ');
printf("= 0\n\n");
}
}
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define S(a) ((a)*(a))
using namespace std;
struct Point{LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}};
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getcircle(Point A,Point B,Point C){
LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
LD F=-(S(x1)+S(y1)+D*x1+E*y1);
// printf("(%.3lf,%.3lf), D=%.3lf E=%.3lf F=%.3lf\n",D/2.0,E/2.0,D,E,F);
return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
#define abs(x) (x<0?-x:x)
#define sakura(x) (x<0?'-':'+')
inline void print(Point O,LD r){
LD a=-O.x,b=-O.y,c=r,d=-2.0*O.x,e=-2.0*O.y,f=S(O.x)+S(O.y)-S(r);
if(a!=0)printf("(x %c %.3lf)^2 ",sakura(a),abs(a));
else printf("x^2 ");
if(b!=0)printf("+ (y %c %.3lf)^2 ",sakura(b),abs(b));
else printf("+ y^2 ");
printf("= %.3lf^2\n",c);
printf("x^2 + y^2");
if(d!=0)printf(" %c %.3lf%c",sakura(d),abs(d),'x');
if(e!=0)printf(" %c %.3lf%c",sakura(e),abs(e),'y');
if(f!=0)printf(" %c %.3lf%c",sakura(f),abs(f),' ');
printf("= 0\n\n");
}
int main(){
// freopen("123.txt","r",stdin);
LD a,b,c,d,e,f;
while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
Circle C=getcircle(Point(a,b),Point(c,d),Point(e,f));print(C.O,C.r);
}
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return a*dcmp(a);}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LD LDin(){
LD X=0,Y=1.0;int f=0;char c=getchar();
while(c<'0'||c>'9'){f|=c=='-';c=getchar();}
while(c>='0'&&c<='9')X=X*10+(c^48),c=getchar();
if(c=='.'){c=getchar();while(c>='0'&&c<='9')X+=(Y/=10)*(c^48),c=getchar();}
return f?-X:X;
}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){x=LDin(),y=LDin();}
inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Vector a,Vector b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}
inline Point turn_P(Point a,LD theta){
LD x=a.x*cos(theta)+a.y*sin(theta);
LD y=-a.x*sin(theta)+a.y*cos(theta);
return Point(x,y);
}
inline Point cross_LL(Point a,Point b,Point c,Point d){
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));
}
inline LD dis_PL(Point p,Point a,Point b){
if(a==b)return Len(p-a);
Vector x=p-a,y=p-b,z=b-a;
if(dcmp(Dot(x,z))<0)return Len(x);
if(dcmp(Dot(y,z))>0)return Len(y);
return Abs(Cro(x,z)/Len(z));
}
inline Point FootPoint(Point p,Point a,Point b){
Vector x=p-a,y=p-b,z=b-a;
LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);
return a+z*(len1/(len1+len2));
}
inline LD calc(Point A,Point B,Point O,LD R){
if((A==O)||(B==O))return 0;
Re op=(dcmp(Cro(A-O,B-O))>0)?1:-1;LD ans=0;
Vector x=A-O,y=B-O;
Re flag1=(int)(dcmp(Len(x)-R)>0),flag2=(int)(dcmp(Len(y)-R)>0);
if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;
else if(flag1&&flag2){
if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;
else{
if(dcmp(Cro(A-O,B-O))>0)swap(A,B);
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
}
}
else{
if(flag1)swap(A,B);
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=(dcmp(Cro(A-O,B-O))>0)?(F-z):(F+z);
ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
}
return ans*op;
}
Point V,P[N];LD h,t,g,v0,ans,theta;int n;Point O;LD R;
int main(){
// freopen("123.txt","r",stdin);
while(~scanf("%lf",&O.x)){
O.y=LDin(),v0=LDin(),theta=LDin(),t=LDin(),g=LDin(),R=LDin();
if(!dcmp(O.x)&&!dcmp(O.y)&&!dcmp(v0)&&!dcmp(theta)&&!dcmp(t)&&!dcmp(g)&&!dcmp(R))break;
theta=theta/180.0*Pi,O.x+=t*v0*cos(theta),O.y+=t*v0*sin(theta)-0.5*g*t*t,ans=0;
// printf("O=(%.2lf,%.2lf), R=%d\n",O.x,O.y,R);
in(n);for(Re i=1;i<=n;++i)P[i].in();
for(Re i=1;i<=n;++i)ans+=calc(P[i],P[i<n?i+1:1],O,R);
if(!dcmp(ans))puts("0.00");
else printf("%.2lf\n",Abs(ans));
}
}
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LD double
#define LL long long
#define Re register int
#define Rd register LD
#define Vector Point
using namespace std;
const int N=2003;
const LD eps=1e-9;
int n,m;map<LD,LD>vis;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
};
struct Segment{
LD L,R;Segment(LD l=0,LD r=0){L=l,R=r;}
inline bool operator<(Segment O)const{return L!=O.L?L<O.L:R<O.R;}
}Seg[N];
struct Triangle{
LD x,y,m,L,R,D,U;
inline void in(){scanf("%lf%lf%lf",&x,&y,&m),L=x,R=x+m,D=y,U=y+m;}
}C[N],C_[N];
inline bool cmp(Triangle A,Triangle B){return A.m<B.m;}
inline LD F(Rd Y){
if(vis[Y])return vis[Y];
Re t=0;Rd ans=0;
for(Re i=1;i<=n;++i)
if(dcmp(Y-C[i].D)>=0&&dcmp(Y-C[i].U)<0){
Rd tmp=C[i].U-Y;
if(dcmp(tmp)>0)Seg[++t]=Segment(C[i].x,C[i].x+tmp);
}
if(!t)return 0.0;
sort(Seg+1,Seg+t+1);
for(Re i=1,j;i<=t;i=j+1){
Rd L=Seg[i].L,R=Seg[i].R;j=i;
while(j<t&&Seg[j+1].L<=R)++j,R=max(R,Seg[j].R);
ans+=R-L;
}
return vis[Y]=ans;
}
inline LD Simpson(Rd L,Rd R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(Rd L,Rd R,Rd now){
Rd mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
if(!dcmp(now-FL-FR))return now;
return sakura(L,mid,FL)+sakura(mid,R,FR);
}
inline int TIT(Triangle A,Triangle B){
return A.L>=B.L&&A.R<=B.R&&A.D>=B.D&&A.U<=B.U&&dcmp(A.R-(B.x+B.U-A.y))<=0;
}
LD ans,YY[N<<1];
int main(){
// freopen("456.txt","r",stdin);
scanf("%d",&m);Re t=0;
for(Re i=1;i<=m;++i)C_[i].in();
sort(C_+1,C_+m+1,cmp),C[++n]=C_[m];
for(Re i=m-1;i>=1;--i){
Re flag=1;
for(Re j=1;j<=n&&flag;++j)if(TIT(C_[i],C[j]))flag=0;
if(flag)C[++n]=C_[i];
}
for(Re i=1;i<=n;++i)YY[++t]=C[i].D,YY[++t]=C[i].U;
sort(YY+1,YY+t+1);
for(Re i=2;i<=t;++i)
if(dcmp(YY[i]-YY[i-1])>0){
Rd D=YY[i-1],U=YY[i]-2*eps;
ans+=sakura(D,U,Simpson(D,U));
}
printf("%.1lf",ans);
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define Vector Point
#define Re register int
using namespace std;
const int N=1e4+3;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
struct Point{LD x,y;Point(LD X=0,LD Y=0):x(X),y(Y){}}Poi[N],cp[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}
inline Vector Normal(Vector a){LD L=Len(a);return Vector(-a.y/L,a.x/L);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline Vector operator/(Vector a,LD b){return Vector(a.x/b,a.y/b);}
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline bool cmp2(Vector a,Vector b){
LD pan=Cro(a-Poi[0],b-Poi[0]);
return pan>0||(pan==0&&Len(a-Poi[0])<Len(b-Poi[0]));
};
inline int ConvexHull(Point *P,Re n,Point *cp){
sort(P+1,P+n+1,cmp1);
Re t=0;
for(Re i=1;i<=n;++i){
while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
Re St=t;
for(Re i=n-1;i>=1;--i){
while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
return --t;
}
int n;LD ans;
int main(){
// freopen("123.txt","r",stdin);
scanf("%d",&n);
for(Re i=1;i<=n;++i)scanf("%lf%lf",&Poi[i].x,&Poi[i].y);
Re cnt=ConvexHull(Poi,n,cp);
for(Re i=1;i<=cnt;++i)ans+=Len(cp[i<cnt?i+1:1]-cp[i]);
printf("%.2lf\n",ans);
}
#include<algorithm>
#include<cstdio>
#include<set>
#define LL long long
#define Vector Point
#define Re register int
#define IT set<Point>::iterator
using namespace std;
const int inf=2e9;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Point{
LL x,y;Point(LL X=0,LL Y=0){x=X,y=Y;}
inline void In(){Re X,Y;in(X),in(Y),x=X,y=Y;}
inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
}P;
inline LL Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
struct ConvexHull{
int op;set<Point>s;
inline int PIP(Point P){
IT it=s.lower_bound(Point(P.x,-inf));
if(it==s.end())return 0;
if(it->x==P.x)return (P.y-it->y)*op<=0;
if(it==s.begin())return 0;
IT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;
}
inline int judge(IT it){
IT j=it,k=it;
if(j==s.begin())return 0;--j;
if(++k==s.end())return 0;
return Cro(*it-*j,*k-*j)*op>=0;
}
inline void insert(Point P){
if(PIP(P))return;
IT tmp=s.lower_bound(Point(P.x,-inf));if(tmp!=s.end()&&tmp->x==P.x)s.erase(tmp);
s.insert(P);IT it=s.find(P),p=it;
if(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;s.erase(tmp);}}
if((p=++it)!=s.end())while(judge(p)){IT tmp=p++;s.erase(tmp);}
}
}up,down;
int x,y,T,op;
int main(){
// freopen("123.txt","r",stdin);
in(T),up.op=1,down.op=-1;
while(T--){
in(op),P.In();
if(op<2)up.insert(P),down.insert(P);
else puts((up.PIP(P)&&down.PIP(P))?"YES":"NO");
}
}
//#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LD double
#define LL long long
#define Re register int
#define Rd register LD
#define Vector Point
using namespace std;
const int N=2003;
const LD eps=1e-13;
int n,m;map<LD,LD>vis;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
};
struct Segment{
LD L,R;Segment(LD l=0,LD r=0){L=l,R=r;}
inline bool operator<(Segment O)const{return L!=O.L?L<O.L:R<O.R;}
}Seg[N];
struct Circle{
LD x,y,r,L,R,D,U;
inline void in(){scanf("%lf%lf%lf",&x,&y,&r),L=x-r,R=x+r,D=y-r,U=y+r;}
inline bool operator<(Circle B)const{return D<B.D;}
}C[N],C_[N];
inline bool cmp(Circle A,Circle B){return A.r<B.r;}
inline LD dis(Circle A,Circle B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
inline LD SS(Rd x){return x*x;}
inline LD F(Rd Y){
if(vis[Y])return vis[Y];
Re t=0;Rd ans=0;
for(Re i=1;i<=n;++i)
if(dcmp(Y-C[i].D)>0&&dcmp(Y-C[i].U)<0){
Rd tmp=sqrt(SS(C[i].r)-SS(C[i].y-Y));
if(dcmp(tmp)>0)Seg[++t]=Segment(C[i].x-tmp,C[i].x+tmp);
}
if(!t)return 0.0;
sort(Seg+1,Seg+t+1);
for(Re i=1,j;i<=t;i=j+1){
Rd L=Seg[i].L,R=Seg[i].R;j=i;
while(j<t&&Seg[j+1].L<=R)++j,R=max(R,Seg[j].R);
ans+=R-L;
}
return vis[Y]=ans;
}
inline LD Simpson(Rd L,Rd R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(Rd L,Rd R,Rd now){
Rd mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
if(!dcmp(now-FL-FR))return now;
return sakura(L,mid,FL)+sakura(mid,R,FR);
}
LD ans;
int main(){
// freopen("789.txt","r",stdin);
scanf("%d",&m);
for(Re i=1;i<=m;++i)C_[i].in();
sort(C_+1,C_+m+1,cmp),C[++n]=C_[m];
for(Re i=m-1;i>=1;--i){
Re flag=1;
for(Re j=1;j<=n&&flag;++j)
if(dcmp(C_[i].r-C[j].r+dis(C_[i],C[j]))<=0)flag=0;
if(flag)C[++n]=C_[i];
}
sort(C+1,C+n+1);
for(Re i=1,j;i<=n;i=j+1){
Rd D=C[i].D,U=C[i].U;j=i;
while(j<n&&C[j+1].D<=U)++j,U=max(U,C[j].U);
ans+=sakura(D,U,Simpson(D,U));
}
printf("%.3lf",ans);
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Rd register LD
#define Re register int
using namespace std;
const int N=50003;
const LD eps=1e-8;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
}cp[N],Poi[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return Dot(a,a);}
inline Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
inline bool cmp(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
inline int ConvexHull(Point *P,Re n,Point *cp){
sort(P+1,P+n+1,cmp);
Re t=0;
for(Re i=1;i<=n;++i){
while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
Re St=t;
for(Re i=n-1;i>=1;--i){
while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
return --t;
}
int n;
int main(){
// freopen("123.txt","r",stdin);
scanf("%d",&n);
for(Re i=1;i<=n;++i)Poi[i].in();
Re cnt=ConvexHull(Poi,n,cp);
Rd Ans=Len(cp[2]-cp[1]);
for(Re i=1,j=3;i<=cnt;++i){
while(dcmp(Cro(cp[i+1]-cp[i],cp[j]-cp[i])-Cro(cp[i+1]-cp[i],cp[j+1]-cp[i]))<0)j=j<cnt?j+1:1;
Ans=max(Ans,max(Len(cp[j]-cp[i]),Len(cp[j]-cp[i+1])));
}
printf("%lld\n",(LL)(Ans+0.5));
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
#define S(a) ((a)*(a))
using namespace std;
const int N=1e6+3;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作
int n;
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
}P[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getcircle(Point A,Point B,Point C){
LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
LD F=-(S(x1)+S(y1)+D*x1+E*y1);
return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline int PIC(Circle &C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}
inline void Random(){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}
int main(){
// freopen("123.txt","r",stdin);
scanf("%d",&n);
for(Re i=1;i<=n;++i)P[i].in();
// random_shuffle(P+1,P+n+1);
Random();Circle C=Circle(P[1],0);
for(Re i=2;i<=n;++i)
if(!PIC(C,P[i])){
C=Circle(P[i],0);
for(Re j=1;j<i;++j)
if(!PIC(C,P[j])){
C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
}
}
printf("%.2lf %.2lf %.2lf\n",C.O.x,C.O.y,C.r);
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const LD eps=1e-13;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
LD a,b,c,d,L,R;
inline LD F(LD x){return (c*x+d)/(a*x+b);}
inline LD Simpson(LD L,LD R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(LD L,LD R,LD now){
LD mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
if(!dcmp(now-FL-FR))return now;
return sakura(L,mid,FL)+sakura(mid,R,FR);
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&L,&R);
printf("%lf\n",sakura(L,R,Simpson(L,R)));
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const LD eps=1e-7;
inline int dcmp(LD a,LD eps){return a<-eps?-1:(a>eps?1:0);}
LD a,b,c,d,L,R;
inline LD F(LD x){return (c*x+d)/(a*x+b);}
inline LD Simpson(LD L,LD R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(LD L,LD R,LD now,LD eps){
LD mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
if(!dcmp(now-FL-FR,eps))return now;
return sakura(L,mid,FL,eps/2)+sakura(mid,R,FR,eps/2);
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&L,&R);
printf("%lf\n",sakura(L,R,Simpson(L,R),eps));
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const int N=262144+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作
inline LD Abs(LD a){return a*dcmp(a);}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
inline void out(){printf("%.2lf %.2lf\n",x,y);}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}// 撤销操作�нǡ�
inline Vector Normal(Vector a){return Vector(-a.y,a.x);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}
inline Point turn_P(Point a,LD theta){
LD x=a.x*cos(theta)+a.y*sin(theta);
LD y=-a.x*sin(theta)+a.y*cos(theta);
return Point(x,y);
}
inline Point turn_PP(Point a,Point b,LD theta){
LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
return Point(x,y);
}
inline int pan_PL(Point p,Point a,Point b){
return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;
}
inline LD dis_PL(Point p,Point a,Point b){
if(a==b)return Len(p-a);//AB�غ�
Vector x=p-a,y=p-b,z=b-a;
if(dcmp(Dot(x,z))<0)return Len(x);
if(dcmp(Dot(y,z))>0)return Len(y);
return Abs(Cro(x,z)/Len(z));
}
inline int pan_PL_(Point p,Point a,Point b){
return !dcmp(Cro(p-a,b-a));
}
inline Point FootPoint(Point p,Point a,Point b){
Vector x=p-a,y=p-b,z=b-a;
LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);
return a+z*(len1/(len1+len2));
}
inline Point Symmetry_PL(Point p,Point a,Point b){
return p+(FootPoint(p,a,b)-p)*2;
}
inline Point cross_LL(Point a,Point b,Point c,Point d){
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));
}
inline int pan_cross_L_L(Point a,Point b,Point c,Point d){
return pan_PL(cross_LL(a,b,c,d),c,d);
}
inline int pan_cross_LL(Point a,Point b,Point c,Point d){
LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;
}
inline int PIP(Point *P,Re n,Point a){
Re cnt=0;LD tmp;
for(Re i=1;i<=n;++i){
Re j=i<n?i+1:1;
if(pan_PL(a,P[i],P[j]))return 2;
if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))
tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;
}
return cnt&1;
}
inline int judge(Point a,Point L,Point R){
return dcmp(Cro(L-a,R-a))>0;
}
inline int PIP_(Point *P,Re n,Point a){
if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;
if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;
Re l=2,r=n-1;
while(l<r){
Re mid=l+r+1>>1;
if(judge(P[1],P[mid],a))l=mid;
else r=mid-1;
}
if(judge(P[l],a,P[l+1]))return 0;
if(pan_PL(a,P[l],P[l+1]))return 2;
return 1;
}
inline int judge_PP(Point *A,Re n,Point *B,Re m){
for(Re i1=1;i1<=n;++i1){
Re j1=i1<n?i1+1:1;
for(Re i2=1;i2<=m;++i2){
Re j2=i2<m?i2+1:1;
if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;
if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;// 撤销操作�
}
}
return 1;
}
inline LD PolyArea(Point *P,Re n){
LD S=0;
for(Re i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
return S/2.0;
}
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline int ConvexHull(Point *P,Re n,Point *cp){
sort(P+1,P+n+1,cmp1);
Re t=0;
for(Re i=1;i<=n;++i){
while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
Re St=t;
for(Re i=n-1;i>=1;--i){
while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
return --t;
}
struct Line{
Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);}
}L[N],Q[N];
inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);}
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline int halfcut(Line *L,Re n,Point *P){
sort(L+1,L+n+1);Re m=n;n=0;
for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
Re h=1,t=0;
for(Re i=1;i<=n;++i){
while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;
while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;
Q[++t]=L[i];
}
while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
n=0;
for(Re i=h;i<=t;++i)P[++n]=cross(Q[i],Q[i<t?i+1:h]);
return n;
}
Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){
for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
while(i<=n)++t,V[t]=V[t-1]+V1[i++];
while(j<=m)++t,V[t]=V[t-1]+V2[j++];
return t;
}
#define S(a) ((a)*(a))
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getCircle(Point A,Point B,Point C){
LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
LD F=-(S(x1)+S(y1)+D*x1+E*y1);
return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline Circle getcircle(Point A,Point B,Point C){
Point P1=(A+B)*0.5,P2=(A+C)*0.5;
Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
return Circle(O,Len(A-O));
}
inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}
inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}
inline Circle Min_Circle(Point *P,Re n){
// random_shuffle(P+1,P+n+1);
Random(P,n);Circle C=Circle(P[1],0);
for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){
C=Circle(P[i],0);
for(Re j=1;j<i;++j)if(!PIC(C,P[j])){
C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
}
}
return C;
}
inline LD calc(Point A,Point B,Point O,LD R){
if(A==O||B==O)return 0;
Re op=dcmp(Cro(A-O,B-O))>0?1:-1;LD ans=0;
Vector x=A-O,y=B-O;
Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0;
if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;
else if(flag1&&flag2){
if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;
else{
if(dcmp(Cro(A-O,B-O))>0)swap(A,B);
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
}
}
else{
if(flag1)swap(A,B);
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z;
ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
}
return ans*op;
}
int main(){}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3,inf=1e8;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Point{
LD x,y;LD k;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
inline void print(Re op=0){printf("(%.2lf %.2lf) ",x,y);if(op)puts("");}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline int ConvexHull(Point *P,Re n,Point *cp){
sort(P+1,P+n+1,cmp1);
Re t=0;
for(Re i=1;i<=n;++i){
while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
Re St=t;
for(Re i=n-1;i>=1;--i){
while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
return --t;
}
inline int judge(Point a,Point L,Point R){
return dcmp(Cro(L-a,R-a))>0;
}
inline int PIL(Point a,Point b,Point p){
return !dcmp(Cro(p-a,b-a))&&dcmp(Cro(p-a,p-b))<0;
}
inline int PIP(Point *P,Re n,Point a){
if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;
if(PIL(P[1],P[2],a)||PIL(P[1],P[n],a))return 1;
Re l=2,r=n-1;
while(l<r){
Re mid=l+r+1>>1;
if(judge(P[1],P[mid],a))l=mid;
else r=mid-1;
}
if(judge(P[l],a,P[l+1]))return 0;
if(PIL(P[l],P[l+1],a))return 1;
return 1;
}
Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){
for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
while(i<=n)++t,V[t]=V[t-1]+V1[i++];
while(j<=m)++t,V[t]=V[t-1]+V2[j++];
return t;
}
int n,m,T;Point v,P1[N],P2[N],cp1[N],cp2[N];Vector V[N<<1];
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T);
for(Re i=1;i<=n;++i)P1[i].in();
for(Re i=1;i<=m;++i)P2[i].in(),P2[i].x=-P2[i].x,P2[i].y=-P2[i].y;
Re cnt1=ConvexHull(P1,n,cp1),cnt2=ConvexHull(P2,m,cp2);
Re cnt=Mincowski(cp1,cnt1,cp2,cnt2,V);
while(T--)v.in(),printf("%d\n",PIP(V,cnt,v));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline int judge(Point a,Point L,Point R){
return dcmp(Cro(L-a,R-a))>0;
}
inline Point cross(Point a,Point b,Point c,Point d){
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));
}
inline LD PolyArea(Point *P,Re n){
LD ans=0;
for(Re i=1;i<=n;++i)ans+=Cro(P[i],P[i<n?i+1:1]);
return ans/2.0;
}
struct Line{
Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}
}Q[N<<1];
inline int judge(Point a,Line L){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}
inline int halfcut(Line *L,Re n,Point *P){
sort(L+1,L+n+1);Re m=0;
for(Re i=1;i<=n;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++m]=L[i];
Re h=1,t=0;
for(Re i=1;i<=m;++i){
while(h<t&&judge(cross(Q[t],Q[t-1]),L[i]))--t;
while(h<t&&judge(cross(Q[h],Q[h+1]),L[i]))++h;
Q[++t]=L[i];
}
while(h<t&&judge(cross(Q[t],Q[t-1]),Q[h]))--t;
while(h<t&&judge(cross(Q[h],Q[h+1]),Q[t]))++h;
m=0;
for(Re i=h;i<=t;++i)P[++m]=cross(Q[i],Q[i<t?i+1:h]);
return m;
}
int n,m;Point P[N],PP[N<<1];Line L[N<<1];
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)P[i].in();P[n+1]=P[1];
for(Re i=2;i<=n;++i){
Point tmp=P[1]-P[2]-P[i]+P[i+1];
LD a=tmp.y,b=-tmp.x,c=Cro(P[1],P[2])-Cro(P[i],P[i+1]);//ax+by+c<=0
if(!dcmp(a)&&!dcmp(b)){
if(dcmp(c)<=0)continue;
else{puts("0");return 0;}
}
if(!dcmp(a)){//by+c<=0
if(b>0)L[++m]=Line(Point(1,-c/b),Point(0,-c/b));//y<=-c/b
else L[++m]=Line(Point(0,-c/b),Point(1,-c/b));//y>=-c/b
}
else if(!dcmp(b)){//ax+c<=0
if(a>0)L[++m]=Line(Point(-c/a,0),Point(-c/a,1));//x<=-c/a
else L[++m]=Line(Point(-c/a,1),Point(-c/a,0));//x>=-c/a
}
else if(b>0)L[++m]=Line(Point(1,-a/b-c/b),Point(0,-c/b));//y<=-a/b*x-c/b
else L[++m]=Line(Point(0,-c/b),Point(1,-a/b-c/b));//y>=-a/b*x-c/b
}
for(Re i=1;i<=n;++i)L[++m]=Line(P[i],P[i+1]);
Re cnt=halfcut(L,m,PP);
printf("%.4lf\n",PolyArea(PP,cnt)/PolyArea(P,n));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=610;
const LD eps=1e-8,Pi=acos(-1);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
inline void print(){printf("%.2lf %.2lf\n",x,y);}
}P[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return Dot(a,a);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD x){return Vector(a.x*x,a.y*x);}
inline Point cross(Point a,Point b,Point c,Point d){
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));
}
inline int judge(Point a,Point L,Point R){
return dcmp(Cro(L-a,R-a))>0;
}
struct Line{
Point a,b;LD k;int id;Line(Point A=Point(0,0),Point B=Point(0,0)){id=0,a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}
}Q[N];
inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline void halfcut(Line *L,Re &n){
sort(L+1,L+n+1);Re m=n;n=0;
for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
Re h=1,t=0;
for(Re i=1;i<=n;++i){
while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;
while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;
Q[++t]=L[i];
}
while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
n=0;
for(Re i=h;i<=t;++i)L[++n]=Q[i];
}
inline Point turnP(Point a,LD theta){
LD x=a.x*cos(theta)+a.y*sin(theta);
LD y=a.y*cos(theta)-a.x*sin(theta);
return Point(x,y);
}
inline Line get_midL(Point a,Point b){
Point M=a+((b-a)*0.5);
return Line(M,M+turnP(a-b,Pi/2.0));
}
int n,m,T,st,ed;Point a,b,c,d,x0,A[N];Line L[N];
struct Dijkstra{
int o,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[N*N];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
struct QWQ{int x,d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void CL(){memset(head,0,sizeof(head)),o=0;}
inline int dijkstra(Re st,Re ed){
for(Re i=0;i<=n;++i)dis[i]=2e9,pan[i]=0;
Q.push((QWQ){st,dis[st]=1});
while(!Q.empty()){
Re x=Q.top().x;Q.pop();
if(pan[x])continue;
pan[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if(dis[to=a[i].to]>dis[x]+a[i].w)
Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
}
return dis[ed];
}
}T1;
int main(){
// freopen("456.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d",&n),c.in(),x0.in(),T1.CL();
if(!n){puts("0");continue;}
a=Point(0,0),b=Point(c.x,0),d=Point(0,c.y);
for(Re i=1;i<=n;++i){
A[i].in();
if(A[i].x>c.x||A[i].y>c.y){--i,--n;continue;}
if(dcmp(Len(A[i]-x0)-Len(A[st]-x0))<0)st=i;
}
// printf("st=%d\n",st);
for(Re i=1;i<=n;++i){
Re m=0;
for(Re j=1;j<=n;++j)
if(i!=j)L[++m]=get_midL(A[i],A[j]),L[m].id=j;
L[++m]=Line(a,b),L[++m]=Line(b,c),L[++m]=Line(c,d),L[++m]=Line(d,a);
halfcut(L,m);
for(Re j=1;j<=m;++j)T1.add(i,L[j].id,L[j].id>0);
}
printf("%d\n",T1.dijkstra(st,ed));
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return a*dcmp(a);}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Point{
LL x,y;Point(LL X=0,LL Y=0){x=X,y=Y;}
inline void In(){Re X,Y;in(X),in(Y),x=X,y=Y;}
inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
};
inline LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LL Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt((LD)Dot(a,a));}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Vector a,Vector b){return a.x==b.x&&a.y==b.y;}
struct Splay{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
int O,root;queue<int>Q;LD ans;
struct QAQ{int fa,ps[2];Point v;}tr[N];
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
}
inline void splay(Re p){
for(Re fa;pf;rotate(p))
if(tr[fa=pf].fa)rotate(which(p)==which(fa)?fa:p);
root=p;
}
inline void CL(Re p){tr[p].v=Point(),pf=pl=pr=0,p=0;}
inline int New(){
Re p;
if(Q.empty())p=++O;
else p=Q.front(),Q.pop();
return p;
}
inline void del(Re p){CL(p),Q.push(p);}
inline int pre(Re p){p=pl;while(pr)p=pr;return p;}
inline int nex(Re p){p=pr;while(pl)p=pl;return p;}
inline void insert(Point v){
Re p=root,fa=0;
while(p)fa=p,p=tr[p].ps[!(pv<v)];
p=New(),pv=v,pf=fa;
if(fa)tr[fa].ps[!(tr[fa].v<v)]=p;
splay(p);Re p1=0,p2=0;
if(pl)p1=pre(p);if(pr)p2=nex(p);
if(p1&&p2)ans-=Len(tr[p2].v-tr[p1].v);
if(p1)ans+=Len(v-tr[p1].v);
if(p2)ans+=Len(v-tr[p2].v);
}
inline void erase(Point v){
Re p=root;
while(!(pv==v))p,p=tr[p].ps[!(pv<v)];
splay(p);
Re p1=0,p2=0;
if(pl)p1=pre(p);if(pr)p2=nex(p);
if(p1&&p2)ans+=Len(tr[p2].v-tr[p1].v);
if(p1)ans-=Len(v-tr[p1].v);
if(p2)ans-=Len(v-tr[p2].v);
if(!pl&&!pr){root=0,del(p);return;}
if(!pl||!pr){tr[root=pl+pr].fa=0,del(p);return;}
splay(pre(p)),tr[root].ps[1]=pr,tr[pr].fa=root,del(p);
}
};
#define IT set<Point>::iterator
struct ConvexHull{
int op;set<Point>s;LD ans;//Splay ss;
inline void Insert(Point P){
s.insert(P);IT p=s.find(P);
Re o1=0,o2=0;IT p1=p,p2=p;
if(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;
if(o1&&o2)ans-=Len(*p2-*p1);
if(o1)ans+=Len(*p-*p1);
if(o2)ans+=Len(*p-*p2);
}
inline void Erase(IT p){
Re o1=0,o2=0;IT p1=p,p2=p;
if(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;
if(o1&&o2)ans+=Len(*p2-*p1);
if(o1)ans-=Len(*p-*p1);
if(o2)ans-=Len(*p-*p2);
s.erase(p);
}
inline int PIP(Point P){
IT it=s.lower_bound(Point(P.x,-2e9));
if(it==s.end())return 0;
if(it->x==P.x)return (P.y-it->y)*op<=0;
if(it==s.begin())return 0;
IT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;
}
inline int judge(IT it){
IT j=it,k=it;
if(j==s.begin())return 0;--j;
if(++k==s.end())return 0;
return Cro(*it-*j,*k-*j)*op>=0;
}
inline void insert(Point P){
if(PIP(P))return;
IT tmp=s.lower_bound(Point(P.x,-2e9));if(tmp!=s.end()&&tmp->x==P.x)Erase(tmp);//ss.erase(*tmp),s.erase(tmp);
Insert(P);/*s.insert(P),ss.insert(P);*/IT it=s.find(P),p=it;
if(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}}
if((p=++it)!=s.end())while(judge(p)){IT tmp=p++;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}
}
}up,down;
int n,x,T,X[N],op[N],vis[N];LD Ans[N];Point P[N];
int main(){
// freopen("123.txt","r",stdin);
in(x),P[0].In(),up.op=1,down.op=-1;
up.insert(P[0]),down.insert(P[0]);
up.insert(Point(0,0)),down.insert(Point(0,0));
up.insert(Point(x,0)),down.insert(Point(x,0));
in(n);for(Re i=1;i<=n;++i)P[i].In();
in(T);for(Re i=1;i<=T;++i){in(op[i]);if(op[i]<2)in(x),vis[X[i]=x]=1;}
for(Re i=1;i<=n;++i)if(!vis[i])up.insert(P[i]),down.insert(P[i]);
for(Re i=T;i>=1;--i)
if(op[i]<2)up.insert(P[X[i]]),down.insert(P[X[i]]);
else Ans[i]=up.ans+Len(*up.s.begin()-*down.s.begin())+Len(*--up.s.end()-*--down.s.end());
for(Re i=1;i<=T;++i)if(op[i]>1)printf("%.2lf\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define y1 ORZ_HYJ_AK_IOI
#define LL long long
#define Re register int
using namespace std;
const int N=1e4;
int a,b,c,d,n,m,pan1[N+5<<1],pan2[N+5<<1];LL ans;
struct Line{int x,y1,y2,k;inline bool operator<(Line O)const{return x==O.x?k>O.k:x<O.x;}}A[N+5<<1],B[N+5<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i){
in(a),in(b),in(c),in(d);
A[++m]=(Line){a,b,d,1},B[m]=(Line){b,a,c,1};
A[++m]=(Line){c,b,d,0},B[m]=(Line){d,a,c,0};
}
sort(A+1,A+m+1);
sort(B+1,B+m+1);
for(Re i=1;i<=m;++i){
if(A[i].k)for(Re j=A[i].y1;j<A[i].y2;++j)ans+=(!pan1[j+N]),++pan1[j+N];
else for(Re j=A[i].y1;j<A[i].y2;++j)--pan1[j+N],ans+=(!pan1[j+N]);
if(B[i].k)for(Re j=B[i].y1;j<B[i].y2;++j)ans+=(!pan2[j+N]),++pan2[j+N];
else for(Re j=B[i].y1;j<B[i].y2;++j)--pan2[j+N],ans+=(!pan2[j+N]);
}
printf("%lld\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=2e4+3;
int n,m,ans,Max=10000,x1[N],y1[N],x2[N],y2[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{int S,cnt;}tr[M<<2];
inline void pushup(Re p,Re L,Re R){
if(tr[p].cnt)tr[p].S=R-L+1;
else tr[p].S=(L==R)?0:tr[pl].S+tr[pr].S;
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){tr[p].cnt+=v,pushup(p,L,R);return;}
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p,L,R);
}
}TR1,TR2;
struct Line{
int x,y1,y2,k;Line(Re X=0,Re Y1=0,Re Y2=0,Re K=0){x=X,y1=Y1,y2=Y2,k=K;}
inline bool operator<(const Line &O)const{return x!=O.x?x<O.x:k>O.k;}
}L1[N<<1],L2[N<<1];
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)
in(x1[i]),in(y1[i]),in(x2[i]),in(y2[i]),x1[i]+=Max,y1[i]+=Max,x2[i]+=Max,y2[i]+=Max,
L1[++m]=Line(x1[i],y1[i],y2[i],1),L2[m]=Line(y1[i],x1[i],x2[i],1),
L1[++m]=Line(x2[i],y1[i],y2[i],-1),L2[m]=Line(y2[i],x1[i],x2[i],-1);
sort(L1+1,L1+m+1),sort(L2+1,L2+m+1);
for(Re i=1,j=0;i<=m;i=j+1){
Re last=TR1.tr[1].S;
++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);
while(j+1<=m&&L1[j].x==L1[j+1].x&&L1[j].k==L1[j+1].k)++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);
ans+=abs(last-TR1.tr[1].S);
}
for(Re i=1,j=0;i<=m;i=j+1){
Re last=TR2.tr[1].S;
++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);
while(j+1<=m&&L2[j].x==L2[j+1].x&&L2[j].k==L2[j+1].k)++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);
ans+=abs(last-TR2.tr[1].S);
}
printf("%d\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,T,x1,y1,x2,y2,b[N<<1];LL ans;
struct Line{int x,y1,y2,k;inline bool operator<(const Line &O)const{return x<O.x;}}A[N<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{int cnt,len;}tr[N<<3];
inline void pushup(Re p,Re L,Re R){
if(tr[p].cnt)tr[p].len=b[R+1]-b[L];
else tr[p].len=(L==R)?0:tr[pl].len+tr[pr].len;
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){tr[p].cnt+=v,pushup(p,L,R);return;}
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p,L,R);
}
}TR;
int main(){
in(T);
while(T--){
in(x1),in(y1),in(x2),in(y2);
A[++n]=(Line){x1,y1,y2,1},A[++n]=(Line){x2,y1,y2,-1};
b[++m]=y1,b[++m]=y2;
}
sort(A+1,A+n+1),sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
for(Re i=1;i<n;++i){
Re y1=lower_bound(b+1,b+m+1,A[i].y1)-b,y2=lower_bound(b+1,b+m+1,A[i].y2)-b;
TR.change(1,1,m-1,y1,y2-1,A[i].k);
ans+=(LL)TR.tr[1].len*(A[i+1].x-A[i].x);
}
printf("%lld\n",ans);
}