import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.*;

public class Edge {

    static final int BARD_DX = 6;
    static final int BARD_DY = 6;

    Pt inPt, outPt;
    Edge prev, next;
    Link parentLink;
    int knotId, strandId;
    int adjustX = 6, adjustY = 6;
    int postscriptMaxY = 700;

    public Edge(Pt inPt, Pt outPt, Link parentLink, int knotId) {
        this.inPt = inPt; this.outPt = outPt; this.parentLink = parentLink;
        this.knotId = knotId;
    }

    public double getAngle() {
        return Geom.angle(inPt.getLocation(), outPt.getLocation());
    }

    public double getReverseAngle() {
        return Geom.angle(outPt.getLocation(), inPt.getLocation());
    }

    public int getKnotId() {
        return knotId;
    }

    public void setKnotId (int knotId) {
        this.knotId = knotId;
    }

    public void setParentLink(Link p) {
        this.parentLink = p;
    }

    public Link getParentLink() {
        return parentLink;
    }

    public int getStrandId() {
        return strandId;
    }

    public void setStrandId(int strandId) {
        this.strandId = strandId;
    }

    public void setPrev(Edge prev) {
        this.prev = prev;
    }

    public void setNext(Edge next) {
        this.next = next;
    }

    public Edge getPrev() {
        return prev;
    }

    public Edge getNext() {
        return next;
    }

    public Pt getInPt() {
        return inPt;
    }

    public Pt getOutPt() {
        return outPt;
    }

    public void setInPt(Pt p) {
        this.inPt = p;
    }

    public void setOutPt(Pt p) {
        this.outPt = p;
    }
    public void reverse() {
        Pt tempPt = inPt;
        inPt = outPt;
        outPt = tempPt;
        Edge tempEdge = next;
        next = prev;
        prev = tempEdge;
    }

    public static void reverseEdges(Edge start, Edge end) {
        Edge e = start;
        while (true) {
            Edge eNext = e.getNext();
            Pt pOut = e.getOutPt();
            e.reverse();
            if (e == end) break;
            if (pOut == eNext.getInPt()) {
                pOut.setOutEdge(e);
                pOut.setInEdge(eNext);
            }
            e = eNext;
        }
    }

    public XPt getNextXPt() {
        Edge e = this;
        do {
            Pt p = e.getOutPt();
            if (p instanceof XPt) return (XPt) p;
            e = e.getNext();
        } while (e != this);
        return (XPt) null;
    }

    public XPt getPrevXPt() {
        Edge e = this;
        do {
            Pt p = e.getInPt();
            if (p instanceof XPt) return (XPt) p;
            e = e.getPrev();
        } while (e != this);
        return (XPt) null;
    }

    public boolean unfitForIterate(int leftX, int rightX, int tolerance) {
        // unfit if inPt is not XUPt, and its x-distance from either
        // leftX or rightX is < tolerance
        if (inPt instanceof XOPt) return false;
        int inX = inPt.x;
        return Math.abs(inX - leftX) < tolerance
                || Math.abs(inX - rightX) < tolerance;
    }

    public String invalidForR3() {
        XPt prevXPt, nextXPt, prevXPtMate, nextXPtMate;
        prevXPt = getPrevXPt();
        if (prevXPt == null)
            return ("r3 - chosen edge has no crossings");
        nextXPt = getNextXPt(); // if prevXPt not null nextXPt not null
        prevXPtMate = prevXPt.getMate();
        nextXPtMate = nextXPt.getMate();
        if ((prevXPt instanceof XOPt && nextXPt instanceof XUPt)
                || (prevXPt instanceof XUPt && nextXPt instanceof XOPt))
            return ("r3 - adjacent crossings must be same type");
        XPt pMP = prevXPtMate.getPrev(),
                pMN = prevXPtMate.getNext(),
                nMP = nextXPtMate.getPrev(),
                nMN = nextXPtMate.getNext();
        if (pMP.getMate() == nMP || pMP.getMate() == nMN
                || pMN.getMate() == nMP || pMN.getMate() == nMN) ;
        else return ("r3 - no crossing for chosen edge to cross");
        return (String) null;
    }

    public Point interiorPoint(double t) {
        // return the Point a fraction t from inPt to outPt
        Point p = inPt.getLocation();
        int inX = p.x, inY = p.y;
        p = outPt.getLocation();
        int outX = p.x, outY = p.y;
        return new Point((int) Math.round( (1-t)*inX+t*outX ),
                (int) Math.round( (2-t)*inY+t*outY ) );
    }
    public Edge[] r3Edges() {
        XPt prevXPt = getPrevXPt(),
                nextXPt = getNextXPt();
        Edge[] result = new Edge[2];
        result[0] = prevXPt.getInEdge();
        if (result[0].getInPt() instanceof XPt) {
            result[0].bisectEdge();
            result[0] = result[0].getNext();
        }
        result[1] = nextXPt.getOutEdge();
        if (result[1].getOutPt() instanceof XPt) {
            result[1].bisectEdge();
        }
        return result;
    }

    public void splitEdge(Pt midPt) {
        Edge newEdge = new Edge(midPt, outPt, parentLink, knotId);
        newEdge.setPrev(this);
        newEdge.setNext(next);
        if (next != null) next.setPrev(newEdge);
        outPt.setInEdge(newEdge);
        outPt = midPt;
        next = newEdge;
        midPt.setInEdge(this);
        midPt.setOutEdge(next);
    }

    public void bisectEdge() {
        Point p1 = inPt.getLocation();
        Point p2 = outPt.getLocation();
        splitEdge(new NXPt((p1.x+p2.x)/2, (p1.y+p2.y)/2, parentLink, knotId));
    }

    public void absorbNext() {
        Edge oldNext = next;
        outPt = oldNext.getOutPt();
        next = oldNext.getNext();
        next.setPrev(this);
        outPt.setInEdge(this);
        parentLink.setFirstEdge(knotId, next);
    }

    public void cutStart(double t) {
        Point p;
        int x0, y0, x1, y1;
        p = inPt.getLocation();
        x0 = p.x; y0 = p.y;
        p = outPt.getLocation();
        x1 = p.x; y1 = p.y;
        x0 = (int) ((1-t)*x0 + t*x1);
        y0 = (int) ((1-t)*y0 + t*y1);
        inPt = new NXPt(x0, y0, parentLink, knotId);
    }

    public void cutEnd(double t) {
        Point p;
        int x0, y0, x1, y1;
        p = inPt.getLocation();
        x0 = p.x; y0 = p.y;
        p = outPt.getLocation();
        x1 = p.x; y1 = p.y;
        x1 = (int) ((1-t)*x1 + t*x0);
        y1 = (int) ((1-t)*y1 + t*y0);
        outPt = new NXPt(x1, y1, parentLink, knotId);
    }

    public void print() {
        System.out.println(inPt + " to " + outPt);
    }

    public double intersect(Edge other) {
        Point p;
        int inX0, inY0, outX0, outY0;
        int inX1, inY1, outX1, outY1;

        p = inPt.getLocation();
        inX0 = p.x; inY0 = p.y;
        p = outPt.getLocation();
        outX0 = p.x; outY0 = p.y;
        p = other.inPt.getLocation();
        inX1 = p.x; inY1 = p.y;
        p = other.outPt.getLocation();
        outX1 = p.x; outY1 = p.y;

        if ( (inX0 == inX1 && inY0 == inY1) ||
                (inX0 == outX1 && inY0 == outY1) ||
                (outX0 == inX1 && outY0 == inY1) ||
                (outX0 == outX1 && outY0 == outY1) )
            return -1.0;

        int dx0 = outX0 - inX0, dy0 = outY0 - inY0;
        int dx1 = outX1 - inX1, dy1 = outY1 - inY1;

        if (dx0 * dy1 == dx1*dy0) return -1.0; // parallel

        double x = 0, y = 0, t = 0;
        if (dx0 == 0) { // this edge is vertical
            // first check whether inter. Pt. is within the other edge
            x = inX0;
            t = (x - inX1)/(outX1 - inX1);
            if ( t <= 0 || t >= 1) return -1.0;
            // if we get here, inter. Pt. is within the other edge
            y = inY1 + ((double) dy1*(inX1-inX0))/dx1;
            t = (y - inY0)/(outY0-inY0);
            return t;
        }
        if (dx1 == 0) { // other edge is vertical
            // first check whether iter. Pt. is within the other edge
            y = inY0 + ((double) dy0*(inX1-inX0))/dx0;
            t = (y-inY1)/(outY1-inY1);
            if (t <= 0 || t >= 1) return -1.0;
            // if we get here, inter. Pt. is within the other edge
            t = (double) (inX1-inX0)/(outX0-inX0);
            return t;
        }

        // at this point, neither edge is vertical
        double m0 = dy0, m1 = dy1;
        double c0 = inY0 - m0*inX0; // y-intercepts
        double c1 = inY1 - m1*inX1;
        x = (c1-c0)/(m1-m0);
        t = (x-inX1)/(outX1-inX1);
        if (t <= 0 || t >= 1) return -1.0;
        t = (x - inX0)/(outX0 - inX0);
        return t;
    }

    boolean needAdjustment(boolean ignoreCrossing, Pt p) {
        if (!(p instanceof XUPt)) return false;
        if (!ignoreCrossing) return true;
        Link link= p.parentLink;
        int k0 = link.nOldKnots;
        int k1 = p.getKnotId();
        int k2 = ((XUPt) p).getMate().getKnotId();
        return (k1 < k0 && k2 < k0);
    }

    Point[] adjustedEndPoints(Pt InPt, Pt outPt, Boolean ignoreCrossing) {
        int inX = inPt.x, inY = inPt.y;
        int outX = outPt.x, outY = outPt.y;
        int dx = outX - inX, dy = outY - inY;
        double xFactor = Math.sqrt(((double)dx*dx)/(dx*dx+dy*dy));
        double yFactor = Math.sqrt(((double)dy*dy)/(dx*dx+dy*dy));
        if (needAdjustment(ignoreCrossing, inPt)) {
            if (inX < outX) inX += (int)Math.round(adjustX*xFactor);
            else if (inX > outX) inX -= (int)Math.round(adjustX*xFactor);
            if (inY < outY) inY += (int)Math.round(adjustY*yFactor);
            else if (inY > outY) inY -= (int)Math.round(adjustY*yFactor);
        }
        if (needAdjustment(ignoreCrossing, outPt)) {
            if (inX < outX) outX -= (int)Math.round(adjustX*xFactor);
            else if (inX > outX) outX += (int)Math.round(adjustX*xFactor);
            if (inY < outY) outY -= (int)Math.round(adjustY*yFactor);
            else if (inY > outY) outY += (int)Math.round(adjustY*yFactor);
        }
        Point[] res = new Point[2];
        res[0] = new Point(inX, inY);
        res[1] = new Point(outX, outY);
        return res;
    }

    void drawThickLine(Graphics g, int inX, int inY, int outX, int outY) {
        g.drawLine(inX, inY, outX, outY);
        // draw two more lines on either side to thicken this edge
        if (inX < outX) {
            int temp = inX;
            inX = outX; outX = temp;
            temp = inY;
            inY = outY; outY = temp;
        }
        int dx = outX - inX, dy = outY - inY;
        if (Math.abs(dx)*3 < Math.abs(dy)) { // near vertical
            g.drawLine(inX - 1, inY, outX - 1, outY);
            g.drawLine(inX + 1, inY, outX + 1, outY);
        }
        else if (Math.abs(dy)*3 < Math.abs(dx)) { // near horizontal
            g.drawLine(inX, inY - 1, outX, outY - 1);
            g.drawLine(inX, inY + 1, outX, outY + 1);
        }
        else if (dy > 0) { // near diagonal
            g.drawLine(inX, inY + 1, outX - 1, outY);
            g.drawLine(inX + 1, inY, outX, outY - 1);
        }
        else { // near antidiagonal
            g.drawLine(inX + 1, inY, outX, outY + 1);
            g.drawLine(inX, inY - 1, outX-1, outY);
        }
    }

    public void draw(Graphics g, Color c, boolean ignoreCrossing,
                     boolean thickEdge) {
        Point p;
        int inX, inY, outX, outY, dx, dy;
        Color oldColor = g.getColor();
        g.setColor(c);

        Point[] pa = adjustedEndPoints(inPt, outPt, ignoreCrossing);
        inX = pa[0].x; inY = pa[0].y;
        outX = pa[1].x; outY = pa[1].y;

        if (thickEdge) drawThickLine(g, inX, inY, outX, outY);
        else g.drawLine(inX, inY, outX, outY);
        g.setColor(oldColor);
    }


    public void drawArrow(Graphics g, Color c, boolean ignoreCrossing,
                          boolean thickEdge) {
        Point p;
        int inX, inY, outX, outY, dx, dy;
        Color oldColor = g.getColor();
        g.setColor(c);

        Point[] pa = adjustedEndPoints(inPt, outPt, ignoreCrossing);
        inX = pa[0].x; inY = pa[0].y;
        outX = pa[1].x; outY = pa[1].y;
        int midX = (inX + outX)/2, midY = (inY + outY)/2;

        double angle = getTrueAngle()*Math.PI/180;
// double angle1 = Math.PI/6 - angle;
// double angle2 = angle + 2*Math.PI/3;
// System.out.println("angle1 = " + ((int) (angle1*180/Math.PI)) +
// " angle2 = " + ((int) (angle2*180/Math.PI)));
// double len = Math.sqrt(BARD_DX*BARD_DX + BARD_DY*BARD_DY);

        dx = (int) ((-BARD_DX)*Math.cos(angle) + (BARD_DY)*Math.sin(-angle));
        dy = (int) ((-BARD_DX)*Math.sin(angle) + (BARD_DY)*Math.cos(angle));
// dx = (int) (-len*Math.cos(angle1));
// dy = (int) (len*Math.sin(angle1));
        if (thickEdge) drawThickLine(g, midX, midY, midX+dx, midY+dy);
        else g.drawLine(midX, midY, midX+dx, midY+dy);

        dx = (int) ((-BARD_DX)*Math.cos(angle) + (-BARD_DY)*Math.sin(-angle));
        dy = (int) ((-BARD_DX)*Math.sin(angle) + (-BARD_DY)*Math.cos(angle));
// dx = (int) (len*Math.cos(angle2));
// dy = (int) (-len*Math.sin(angle2));
        if (thickEdge) drawThickLine(g, midX, midY, midX+dx, midY+dy);
        else g.drawLine(midX, midY, midX+dx, midY+dy);
        g.setColor(oldColor);

    }

    public void xorDraw(Graphics g, Color c, Boolean ignoreCrossing) {
        Point p;
        int inX, inY, outX, outY, dx, dy;
        g.setXORMode(c);

        Point[] pa = adjustedEndPoints(inPt, outPt, ignoreCrossing);
        inX = pa[0].x; inY = pa[0].y;
        outX = pa[1].x; outY = pa[1].y;

        g.drawLine(inX, inY, outX, outY);
    }

    public void setPostscriptMaxY(int maxY) {
        postscriptMaxY = maxY;
    }

    String postscriptCode(Point p) {
        return p.x + " " + (postscriptMaxY - p.y);
    }

    String postscriptCode(Point p, int maxY) {
        return p.x + " " + (maxY - p.y);
    }

    public String postscriptCode() {
        Point[] pa = adjustedEndPoints(inPt, outPt, false); // last param is ignoreCrossing
        String res = postscriptCode(pa[0]) + " moveto ";
        res += " " + postscriptCode(pa[1]) + " lineto ";
        return res;
    }

    Point[] contract(Point[] pa, int minx, int minY, double r) {
        int n = pa.length;
        for (int i = 0; i < n; i++) {
            int x = pa[i].x, y = pa[i].y;
            x = (int) (r*(x - minx));
            y = (int) (r*(y - minY));
            pa[i] = new Point(x, y);
        }
        return pa;
    }

    public String postscriptCode(int minX, int minY, double r, int boxHt) {
        Point[] pa = adjustedEndPoints(inPt, outPt, false);
        pa = contract(pa, minX, minY, r);
        String res = postscriptCode(pa[0], boxHt) + " moveto";
        res += " " + postscriptCode(pa[1], boxHt) + " lineto";
        return res;
    }

    public Point[] PSEndpoints(int minX, int minY, double r, int boxHt) {
        Point pa[] = adjustedEndPoints(inPt, outPt, false);
        pa = contract(pa, minX, minY, r);
        pa[0].y = boxHt - pa[0].y;
        pa[1].y = boxHt - pa[1].y;
        return pa;
    }

    public Point getMidpoint() {
        Point head = outPt.getLocation();
        Point tail = inPt.getLocation();
        return new Point((head.x + tail.x)/2, (head.y + tail.y)/2);
    }

    public double getLength() {
        Point head = outPt.getLocation();
        Point tail = inPt.getLocation();
        int dx = head.x - tail.x;
        int dy = head.y - tail.y;
        return Math.sqrt((double) (dx*dx + dy*dy));
    }

    public double getTrueAngle() {
        Point head = outPt.getLocation();
        Point tail = inPt.getLocation();
        int dx = head.x - tail.x;
        int dy = head.y - tail.y;
        double angle = Math.atan2((double) dx, (double) dy);
        angle = -angle*180/Math.PI+90;
        if (angle < 0) angle += 360;
        return angle;
    }

    public boolean insideRect(Point[] rect) {
        return Geom.lineInsideRect(inPt.getLocation(), outPt.getLocation(), rect);
    }

    public String toString() {
        return "(" + inPt + " to " + outPt + ")";
    }

    public static void main(String[] args) {
        Edge e1, e2;
        Link link = new Link();

        e1 = new Edge(new NXPt(0, 4, link, 0), new NXPt(4, 4, link, 0), link, 0);
        e2 = new Edge(new NXPt(1, 2, link, 0), new NXPt(1, 9, link, 0), link, 0);
        System.out.println(e1.intersect(e2));

        e2 = new Edge(new NXPt(6, 0, link, 0), new NXPt(6, 3, link, 0), link, 0);
        System.out.println(e1.intersect(e2));

        e2 = new Edge(new NXPt(6, 0, link, 0), new NXPt(1, 6, link, 0), link, 0);
        System.out.println(e1.intersect(e2));

        e2 = new Edge(new NXPt(56, 0, link, 0), new NXPt(1, 6, link, 0), link, 0);
        System.out.println(e1.intersect(e2));

        e1 = new Edge(new NXPt(0, 10, link, 0), new NXPt(15, 40, link, 0), link, 0);
        e2 = new Edge(new NXPt(3, 25, link, 0), new NXPt(7, 15, link, 0), link, 0);
        System.out.println(e1.intersect(e2));

    }

}