Question description

teleportation door

can first answer two points
How to judge?
For every target
ax2+bx−y2<=0
ax2+bx−y1>=0
x,y1,y2 (For details, please refer to high school mathematics textbook compulsory 5 linear planning issues)
All semi -flat planes are explained and explained
But the precision of this question is very stuck. It is recommended that EPS open a smaller and then use Long Double, and you need to choose two numbers you like when the analytical previous generation value finds the value.(Use the girl’s birthday with caution)

code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 200005

const long double eps=1e-12;
const long double inf=1e11;
int dcmp(long double x)
{
    if (x<=eps&&x>=-eps) return 0;
    return (x>0)?1:-1;
}
struct Vector
{
    long double x,y;
    Vector(long double X=0,long double Y=0)
    {
        x=X,y=Y;
    }
};
typedef Vector Point;
struct Line
{
    Point p;
    Vector v;
    long double ang;
    Line(Point P=Point(0,0),Vector V=Vector(0,0))
    {
        p=P,v=V;
        ang=atan2(v.y,v.x);
    }
    bool operator < (const Line &a) const
    {
        return ang<a.ang;
    }
};
Vector operator + (Vector a,Vector b) {
   return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b) {
   return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,long double b) {
   return Vector(a.x*b,a.y*b);}

int m,n,l,r,ans;
long double x,y,z;
Point P,Q,p[N];
Line s[N],L[N],q[N];

long double Cross(Vector a,Vector b)
{
    return a.x*b.y-a.y*b.x;
}
bool Onleft(Line l,Point P)
{
    return dcmp(Cross(l.v,P-l.p))>=0;
}
Point GLI(Point P,Vector v,Point Q,Vector w)
{
    Vector u=P-Q;
    long double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
bool check(int mid)
{
    for (int i=1;i<=mid;++i) L[i]=s[i];
    sort(L+1,L+mid+1);
    q[l=r=1]=L[1];
    for (int i=2;i<=mid;++i)
    {
        while (l<r&&!Onleft(L[i],p[r-1]))
            --r;
        while (l<r&&!Onleft(L[i],p[l]))
            ++l;
        q[++r]=L[i];
        if (dcmp(Cross(q[r].v,q[r-1].v))==0)
        {
            --r;
            if (Onleft(q[r],L[i].p))
                q[r]=L[i];
        }
        if (l<r)
            p[r-1]=GLI(q[r-1].p,q[r-1].v,q[r].p,q[r].v);
    }
    while (l<r&&!Onleft(q[l],p[r-1]))
        --r;
    if (r-l<=1) return false;
    else return true;
}
int find()
{
    int l=5,r=n,mid,ans=4;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int read() {
    int ans = 0; char c; bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true; else ans = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ans = ans * 10 + c - '0';
    return ans * (flag ? -1 : 1);
}

int main()
{
    long double a=-1.0,b=4.0;
    scanf("%d",&m);
    s[++n]=Line(Point(0,0),Vector(0,inf));
    s[++n]=Line(Point(0,inf),Vector(-inf,0));
    s[++n]=Line(Point(-inf,inf),Vector(0,-inf));
    s[++n]=Line(Point(-inf,0),Vector(inf,0));
    for (int i=1;i<=m;++i)
    {
        x=read();y=read();z=read();
        if (x<=0) break;

        P=Point(a,(z-x*x*a)/x);
        Q=Point(b,(z-x*x*b)/x);
        s[++n]=Line(Q,P-Q);

        P=Point(a,(y-x*x*a)/x);
        Q=Point(b,(y-x*x*b)/x);
        s[++n]=Line(P,Q-P);
    }
    ans=(find()-4)/2;
    printf("%d\n",ans);
}