#P18848. [Croatian CPC2023] Dražesni Doručak

[Croatian CPC2023] Dražesni Doručak

Dražesni Doručak

题目描述

Mirko 和 Slavko 买了两块馅饼,一块是奶酪馅,一块是肉馅。他们希望每个人都得到每块馅饼的一半。Mirko 决定只沿一条直线切一刀,同时将两块馅饼各分成面积相等的两部分。

两块馅饼分别是两个凸多边形。第一个多边形完全位于 yy 轴左侧,第二个完全位于 yy 轴右侧。给定两个多边形的顶点坐标,请求出满足要求的直线 y=ax+by=ax+b。

第一个样例的示意图

保证满足要求的直线存在且唯一。

输入格式

第一行包含整数 nn(3≤n≤50003\le n\le5000),表示第一个多边形的顶点数。

接下来 nn 行,每行包含两个实数 x,yx,y,表示一个顶点,满足 −1000≤x<0-1000\le x<0,−1000≤y≤1000-1000\le y\le1000。

接下来一行包含整数 mm(3≤m≤50003\le m\le5000),表示第二个多边形的顶点数。

接下来 mm 行,每行包含两个实数 x,yx,y,表示一个顶点,满足 0<x≤10000<x\le1000,−1000≤y≤1000-1000\le y\le1000。

两个多边形的顶点都按逆时针顺序给出。所有坐标恰有三位小数。每个多边形中任意两条相邻边均不平行。

输出格式

输出两个实数 a,ba,b,表示所求直线 y=ax+by=ax+b。

对于每个输出值,与标准答案的绝对误差或相对误差不超过 10−310^{-3} 即被接受。

样例输入 1

3
-6.000 1.000
-2.000 2.000
-5.000 6.000
5
1.000 -1.000
3.000 -2.000
6.000 0.000
4.000 3.000
1.000 2.000

样例输出 1

-0.319961 1.556489

样例输入 2

4
-5.000 -1.000
-3.000 -1.000
-3.000 6.000
-5.000 6.000
4
3.222 2.000
5.000 1.000
5.000 4.000
3.222 3.000

样例输出 2

0.000000 2.500000