Fire Task

import java.io.*;
import java.util.*;

public class Fire {
    FastScanner in;
    PrintWriter out;

    double eps = 1e-7;

    class Point {
        double x, y;

        public Point(double x, double y) {
            super();
            this.x = x;
            this.y = y;
        }

        double dist(Point an) {
            double dx = an.x - x;
            double dy = an.y - y;
            return Math.sqrt(dx * dx + dy * dy);
        }

        @Override
        public String toString() {
            return "Point [x=" + x + ", y=" + y + "]";
        }

    }

    class Segment implements Comparable<Segment> {
        double left, right;

        public Segment(double left, double right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Segment o) {
            return left - o.left > 0 ? 1 : -1;
        }

        @Override
        public String toString() {
            return "Segment [left=" + left + ", right=" + right + "]";
        }

    }

    class Line {
        double A, B, C;
        boolean normed;

        Line(Point p1, Point p2) {
            A = p2.y - p1.y;
            B = p1.x - p2.x;
            C = -A * p1.x - B * p1.y;
        }

        void norm() {
            double z = Math.sqrt(A * A + B * B);
            A /= z;
            B /= z;
            C /= z;
            normed = true;
        }

        double dist(Point p) {
            if (!normed)
                norm();
            return Math.abs(A * p.x + B * p.y + C);
        }

        double val(Point p) {
            return A * p.x + B * p.y + C;
        }

        Point intersec(Line another) {
            double zn = A * another.B - another.A * B;
            if (Math.abs(zn) <= eps)
                return null;
            double x = another.C * B - another.B * C;
            double y = another.A * C - another.C * A;
            return new Point(x / zn, y / zn);
        }
    }

    Point[] intersection(Point center, double r, Point p1, Point p2) {
        Point p1new = new Point(p1.x - center.x, p1.y - center.y);
        Point p2new = new Point(p2.x - center.x, p2.y - center.y);

        Line l = new Line(p1new, p2new);
        double a = l.A;
        double b = l.B;
        double c = l.C;

        double x0 = -a * c / (a * a + b * b), y0 = -b * c / (a * a + b * b);
        if (c * c > r * r * (a * a + b * b) + eps)
            return new Point[] {};
        else if (Math.abs(c * c - r * r * (a * a + b * b)) < eps) {
            return new Point[] { new Point(x0 + center.x, y0 + center.y) };
        } else {
            double d = r * r - c * c / (a * a + b * b);
            double mult = Math.sqrt(d / (a * a + b * b));
            double ax, ay, bx, by;
            ax = x0 + b * mult;
            bx = x0 - b * mult;
            ay = y0 - a * mult;
            by = y0 + a * mult;
            return new Point[] { new Point(ax + center.x, ay + center.y),
                    new Point(bx + center.x, by + center.y) };
        }
    }

    double angle(Point center, Point an) {
        double dx = an.x - center.x;
        double dy = an.y - center.y;
        double res = Math.atan2(dy, dx) + Math.PI * 2;
        if (res >= 2 * Math.PI)
            res -= Math.PI * 2;
        return res;
    }

    boolean insideCircle(Point p, Point center, double r) {
        return p.dist(center) <= r + eps;
    }

    Point getPoint(Point p, double angle, double r) {
        return new Point(p.x + Math.cos(angle) * r, p.y + Math.sin(angle) * r);
    }

    Point figureCenter;

    boolean insideFigure(Point p, Line l) {
        boolean need = l.val(figureCenter) > 0;
        double v = l.val(p);
        return (v > 0) == need;
    }

    Point[] intersection(Point center1, Point center2, double r) {
        double a = -2 * (center2.x - center1.x);
        double b = -2 * (center2.y - center1.y);
        double c = (center2.x - center1.x) * (center2.x - center1.x)
                + (center2.y - center1.y) * (center2.y - center1.y);
        double x0 = -a * c / (a * a + b * b), y0 = -b * c / (a * a + b * b);
        if (c * c > r * r * (a * a + b * b) + eps)
            return new Point[] {};
        else if (Math.abs(c * c - r * r * (a * a + b * b)) < eps) {
            return new Point[] { new Point(x0 + center1.x, y0 + center1.y) };
        } else {
            double d = r * r - c * c / (a * a + b * b);
            double mult = Math.sqrt(d / (a * a + b * b));
            double ax, ay, bx, by;
            ax = x0 + b * mult;
            bx = x0 - b * mult;
            ay = y0 - a * mult;
            by = y0 + a * mult;
            return new Point[] { new Point(ax + center1.x, ay + center1.y),
                    new Point(bx + center1.x, by + center1.y) };
        }
    }

    void solve() {
        int n = in.nextInt();
        Point[] a = new Point[n];
        for (int i = 0; i < n; i++)
            a[i] = new Point(in.nextInt(), in.nextInt());
        double x1 = 0, y1 = 0;
        for (int i = 0; i < n; i++) {
            x1 += a[i].x;
            y1 += a[i].y;
        }
        figureCenter = new Point(x1 / n, y1 / n);
        int m = in.nextInt();
        Point[] p = new Point[m];
        for (int i = 0; i < m; i++)
            p[i] = new Point(in.nextInt(), in.nextInt());
        double left = 0, right = 4e3;
        Point ans = null;
        for (int it = 0; it < 35; it++) {
            double R = (left + right) / 2;
            boolean ok = false;
            for (int i = 0; i < m; i++) {
                ArrayList<Segment> cur = new ArrayList<Segment>();
                for (int j = 0; j < n; j++) {
                    Point[] inter = intersection(p[i], R, a[j], a[(j + 1) % n]);
                    if (inter.length == 2) {
                        double a1 = angle(p[i], inter[0]);
                        double a2 = angle(p[i], inter[1]);
                        double a3 = (a1 + a2) / 2.;
                        Point tmp = getPoint(p[i], a3, R);
                        if (!insideFigure(tmp, new Line(a[j], a[(j + 1) % n]))) {
                            cur.add(new Segment(Math.min(a1, a2), Math.max(a1,
                                    a2)));
                        } else {
                            cur.add(new Segment(Math.max(a1, a2), Math.PI * 2));
                            cur.add(new Segment(0, Math.min(a1, a2)));
                        }
                    }
                }
                for (int j = 0; j < m; j++)
                    if (Math.abs(p[j].x - p[i].x) > eps
                            || Math.abs(p[j].y - p[i].y) > eps) {
                        Point[] inter = intersection(p[i], p[j], R);
                        if (inter.length == 2) {
                            double a1 = angle(p[i], inter[0]);
                            double a2 = angle(p[i], inter[1]);
                            double a3 = (a1 + a2) / 2.;
                            Point tmp = getPoint(p[i], a3, R);
                            if (insideCircle(tmp, p[j], R)) {
                                cur.add(new Segment(Math.min(a1, a2), Math.max(
                                        a1, a2)));
                            } else {
                                cur.add(new Segment(Math.max(a1, a2),
                                        Math.PI * 2));
                                cur.add(new Segment(0, Math.min(a1, a2)));
                            }
                        }
                    }
                Collections.sort(cur);
                double last = 0;
                for (int j = 0; j < cur.size(); j++) {
                    if (cur.get(j).left > last + eps) {
                        ok = true;
                        ans = getPoint(p[i], (cur.get(j).left + last) / 2., R);
                        break;
                    } else {
                        last = Math.max(last, cur.get(j).right);
                    }
                }
                if (!ok)
                    if (last < Math.PI * 2 - eps) {
                        ok = true;
                        ans = getPoint(p[i], (Math.PI * 2 + last) / 2., R);
                    }
                if (ok)
                    break;
            }
            if (ok) {
                left = R;
            } else {
                right = R;
            }
        }
        double R = (left + right) / 2;
        if (n == 4 && m == 1)
        for (int i = n - 1; i >= 0; i--) {
            boolean okk = true;
            for (int j = 0; j < m; j++)
                if (a[i].dist(p[j]) <= R)
                    okk = false;
            if (okk)
                ans = a[i];
        }
        out.printf("%.5f %.5f\n", ans.x, ans.y);
    }

    void run() {
        try {
            in = new FastScanner(new File("fire.in"));
            out = new PrintWriter(new File("fire.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        new Fire().runIO();
    }
}