import java.util.*;

public class ConvexCut {

	public static class Point {
		public double x, y;

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

	// cuts right part of poly (returns left part)
	public static Point[] convexCut(Point[] poly, Point p1, Point p2) {
		int n = poly.length;
		List<Point> res = new ArrayList<>();
		for (int i = 0, j = n - 1; i < n; j = i++) {
			int d1 = orientation(p1.x, p1.y, p2.x, p2.y, poly[j].x, poly[j].y);
			int d2 = orientation(p1.x, p1.y, p2.x, p2.y, poly[i].x, poly[i].y);
			if (d1 >= 0)
				res.add(poly[j]);
			if (d1 * d2 < 0)
				res.add(getLinesIntersection(p1.x, p1.y, p2.x, p2.y, poly[j].x, poly[j].y, poly[i].x, poly[i].y));
		}
		return res.toArray(new Point[res.size()]);
	}

	static int orientation(double ax, double ay, double bx, double by, double cx, double cy) {
		bx -= ax;
		by -= ay;
		cx -= ax;
		cy -= ay;
		double cross = bx * cy - by * cx;
		double EPS = 1e-9;
		return cross < -EPS ? -1 : cross > EPS ? 1 : 0;
	}

	static Point getLinesIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
		double a1 = y2 - y1;
		double b1 = x1 - x2;
		double c1 = -(x1 * y2 - x2 * y1);
		double a2 = y4 - y3;
		double b2 = x3 - x4;
		double c2 = -(x3 * y4 - x4 * y3);
		double det = a1 * b2 - a2 * b1;
		double x = -(c1 * b2 - c2 * b1) / det;
		double y = -(a1 * c2 - a2 * c1) / det;
		return new Point(x, y);
	}

	public static void main(String[] args) {

	}
}