CF70D Professor's task

题意

显然极角序是能\(A\)的，然而我非要用水平序。

code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
typedef long long ll;
int Q;
bool flag;
map<int,int>down,up;
inline pii getvec(pii a,pii b){return mkp(b.fir-a.fir,b.sec-a.sec);}
inline ll calc(pii a,pii b){return 1ll*a.fir*b.sec-1ll*a.sec*b.fir;}
inline bool check_down(int x,int y)
{
    if(down.empty())return 0;
    if(down.count(x))return y>=down[x];
    if(x<down.begin()->fir||x>(--down.end())->fir)return 0;
    map<int,int>::iterator it1=down.lower_bound(x),it2;
    it2=it1;it1--;
    return calc(getvec(*it1,*it2),getvec(*it1,mkp(x,y)))>=0;
}
inline bool check_up(int x,int y)
{
    if(up.empty())return 0;
    if(up.count(x))return y<=up[x];
    if(x<up.begin()->fir||x>(--up.end())->fir)return 0;
    map<int,int>::iterator it1=up.lower_bound(x),it2;
    it2=it1;it1--;
    return calc(getvec(*it1,*it2),getvec(*it1,mkp(x,y)))<=0;
}
inline void add_down(int x,int y)
{
    if(check_down(x,y))return;
    down[x]=y;
    map<int,int>::iterator it1,it2;
    it1=down.upper_bound(x);it2=it1;
    if(it2!=down.end())
    {
        it2++;
        while(it2!=down.end()&&calc(getvec(mkp(x,y),*it1),getvec(*it1,*it2))<=0)down.erase(it1),it1=it2,it2++;
    }
    it1=down.lower_bound(x),it2=it1;
    if(it1!=down.begin())it2--;
    if(it2!=down.begin())
    {
        it1--,it2--;
        while(it1!=down.begin()&&calc(getvec(mkp(x,y),*it1),getvec(*it1,*it2))>=0)down.erase(it1),it1=it2,it2--;
    }
}
inline void add_up(int x,int y)
{
    if(check_up(x,y))return;
    up[x]=y;
    map<int,int>::iterator it1,it2;
    it1=up.upper_bound(x);it2=it1;
    if(it2!=up.end())
    {
        it2++;
        while(it2!=up.end()&&calc(getvec(mkp(x,y),*it1),getvec(*it1,*it2))>=0)up.erase(it1),it1=it2,it2++;
    }
    it1=up.lower_bound(x),it2=it1;
    if(it1!=up.begin())it2--;
    if(it1!=up.begin())
    {
        it1--,it2--;
        while(it1!=up.begin()&&calc(getvec(mkp(x,y),*it1),getvec(*it1,*it2))<=0)up.erase(it1),it1=it2,it2--;
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%d",&Q);
    while(Q--)
    {
        if(Q==7)flag=1;
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)add_down(x,y),add_up(x,y);
        else puts(check_down(x,y)&&check_up(x,y)?"YES":"NO");
        if(flag)flag=0;
    }
    return 0;
}

CF70D Professor's task

原文：https://www.cnblogs.com/nofind/p/12172476.html