#include using namespace std; const double EPS = 1e-8; bool dEqual(double x,double y) { return fabs(x-y) < EPS; } struct Point { double x, y; bool operator==(const Point &p) const { return dEqual(x, p.x) && dEqual(y, p.y); } bool operator<(const Point &p) const { return y < p.y || (y == p.y && x < p.x); } }; Point operator-(Point p,Point q){ p.x -= q.x; p.y -= q.y; return p; } Point operator+(Point p,Point q){ p.x += q.x; p.y += q.y; return p; } Point operator*(double r,Point p){ p.x *= r; p.y *= r; return p; } double operator*(Point p,Point q){ return p.x*q.x + p.y*q.y; } double len(Point p){ return sqrt(p*p); } double cross(Point p,Point q){ return p.x*q.y - q.x*p.y; } Point inv(Point p){ Point q = {-p.y,p.x}; return q; } enum Orientation {CCW, CW, CNEITHER}; //------------------------------------------------------------------------------ // Colinearity test bool colinear(Point a, Point b, Point c) { return dEqual(cross(b-a,c-b),0); } //------------------------------------------------------------------------------ // Orientation test (When pts are colinear: ccw: a-b-c cw: c-a-b neither: a-c-b) Orientation ccw(Point a, Point b, Point c) { // Point d1 = b - a, d2 = c - b; if (dEqual(cross(d1,d2),0)) if (d1.x * d2.x < 0 || d1.y * d2.y < 0) return (d1 * d1 >= d2*d2 - EPS) ? CNEITHER : CW; else return CCW; else return (cross(d1,d2) > 0) ? CCW : CW; } //------------------------------------------------------------------------------ // Signed Area of Polygon double area_polygon(Point p[], int n) { double sum = 0.0; for (int i = 0; i < n; i++) sum += cross(p[i],p[(i+1)%n]); return sum/2.0; } //------------------------------------------------------------------------------ // Intersection of lines (line segment or infinite line) // (1 == 1 intersection pt, 0 == no intersection pts, -1 == infinitely many int intersect_line(Point a, Point b, Point c, Point d, Point &p,bool segment) { double num1 = cross(d-c,a-c), num2 = cross(b-a,a-c),denom = cross(b-a,d-c); if (!dEqual(denom, 0)) { double r = num1 / denom, s = num2 / denom; if (!segment || (0-EPS <= r && r <= 1+EPS && 0-EPS <= s && s <= 1+EPS)) { p = a + r*(b-a); return 1; } else return 0; } if(!segment) return dEqual(num1,0) ? -1 : 0; // For infinite lines, this is the end if (!dEqual(num1, 0)) return 0; if(b < a) swap(a,b); if(d < c) swap(c,d); if (a.x == b.x) { if (b.y == c.y) { p = b; return 1; } if (a.y == d.y) { p = a; return 1; } return (b.y < c.y || d.y < a.y) ? 0 : -1; } else if (b.x == c.x) { p = b; return 1; } else if (a.x == d.x) { p = a; return 1; } else if (b.x < c.x || d.x < a.x) return 0; return -1; } const int MAX_N = 200; int n; Point p1[MAX_N], p2[MAX_N]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> p1[i].x >> p1[i].y >> p2[i].x >> p2[i].y; } double best = -1; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { for (int k = j+1; k < n; k++) { Point p[3]; int res1 = intersect_line(p1[i], p2[i], p1[j], p2[j], p[0], false); int res2 = intersect_line(p1[i], p2[i], p1[k], p2[k], p[1], false); int res3 = intersect_line(p1[j], p2[j], p1[k], p2[k], p[2], false); if (res1 == 1 && res2 == 1 && res3 == 1) { double temp = len(p[0]-p[1]) + len(p[1]-p[2]) + len(p[2]-p[0]); best = max(temp, best); } } } } if (best < EPS) { cout << "no triangle" << endl; } else { cout << fixed << setprecision(10) << best << endl; } return 0; }