https:\/\/mcpc23.kattis.com\/contests\/mcpc23\/problems\/segmentdrawing<\/a><\/p>\n\n\n\n#include <bits\/stdc++.h>\nusing namespace std;\ntypedef pair<int,int> pii;\n#define f first\n#define s second\ntypedef long long ll;\nint n;\ndouble ans = 0;\nll x[100010], y[100010], l[100010], r[100010];\ndouble minx[100010], maxx[100010];\n\nint main() {\n cin>>n;\n for(int i=0;i<n;i++) {\n cin>>x[i]>>y[i]>>l[i]>>r[i];\n }\n\n stack<pii> S;\n\n for(int i=0;i<n;i++) {\n minx[i] = -1e9;\n while(S.size() && S.top().s < y[i]) {\n pii c = S.top();\n S.pop();\n if(x[i] * (y[i] - c.s) + (c.f - x[i]) * y[i] > r[i] * (y[i] - c.s)) {\n cout<<-1<<endl;\n return 0;\n }\n double cx = x[i] + 1.0 * (c.f - x[i]) \/ (y[i] - c.s) * y[i];\n minx[i] = max(minx[i], cx);\n }\n S.push(make_pair(x[i],y[i]));\n }\n while(!S.empty())S.pop();\n\n for(int i=n-1;i>=0;i--) {\n maxx[i] = 1e9;\n while(S.size() && S.top().s < y[i]) {\n pii c = S.top();\n S.pop();\n if(x[i] * (y[i] - c.s) + (c.f - x[i]) * y[i] < l[i] * (y[i] - c.s)) {\n cout<<-1<<endl;\n return 0;\n }\n double cx = x[i] + 1.0 * (c.f - x[i]) \/ (y[i] - c.s) * y[i];\n maxx[i] = min(maxx[i], cx);\n }\n S.push(make_pair(x[i],y[i]));\n }\n\n cout<<setprecision(15)<<fixed;\n const double eps = 1e-6;\n for(int i=0;i<n;i++){\n minx[i] = max(minx[i], (double)l[i]);\n maxx[i] = min(maxx[i], (double)r[i]);\n if(minx[i] > maxx[i] + eps) {\n cout<<-1<<endl;\n return 0;\n }\n\n if(minx[i] > x[i]) {\n ans += sqrt(1.0*y[i]*y[i] + 1.0*(minx[i]-x[i])*(minx[i]-x[i]));\n } else if (maxx[i] < x[i]) {\n ans += sqrt(1.0*y[i]*y[i] + 1.0*(maxx[i]-x[i])*(maxx[i]-x[i]));\n } else {\n ans += y[i];\n }\n }\n cout<<ans<<endl;\n return 0;\n}<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"\u4e0a\u4e2a\u6708\u548c\u961f\u53cb\u6253\u4e86MCPC\u3002\u5176\u4e2d\u8fd9\u9053\u9898\u5f53\u65f6\u611f\u89c9\u4e0d\u96be\u5f88\u5feb\u5c31\u8fc7\u4e86\uff0c\u7ed3\u679c\u522b\u7684\u961f\u8fc7\u7684\u4e0d\u662f\u5f88\u591a\uff0c\u53ef\u80fd\u8fd8\u662f\u6bd4\u8f83\u6709\u610f\u601d\u5427\uff01\u6302\u5728 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/1021"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1021"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/1021\/revisions"}],"predecessor-version":[{"id":1022,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/1021\/revisions\/1022"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}