제출 #1359168

#제출 시각아이디문제언어결과실행 시간메모리
1359168tung04885Mixture (BOI20_mixture)C++20
0 / 100
1 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;
const double EPS=1e-9;
const double PI=3.14592;

struct POINT
{
    double x,y;

    void input()
    {
        cin>>x>>y;
    }

    void norm()
    {
        double c=sqrt(x*x+y*y);

        if(c==0) return;

        x/=c;
        y/=c;
    }

    POINT(double a=0,double b=0)
    {
        x=a,y=b;
    }

    POINT operator + (POINT other) const
    {
        return POINT(x+other.x,y+other.y);
    }

    POINT operator - (POINT other) const
    {
        return POINT(x-other.x,y-other.y);
    }

    bool operator < (POINT other) const
    {
        return atan2(y,x)<atan2(other.y,other.x);
    }

    bool operator == (POINT other) const
    {
        return abs(x-other.x)<EPS&&abs(y-other.y)<EPS;
    }
};

double dot(POINT a,POINT b)
{
    return a.x*b.x+a.y*b.y;
}

POINT T1;
int n,q;
POINT a[MAX];
multiset<POINT> s[4];

void nhap()
{
    double z;

    cin>>z;

    T1.input();

    T1.x/=z;
    T1.y/=z;

    cin>>q;
}

int getID(POINT p)
{
    double angle=atan2(p.y,p.x);

    if(angle<0) angle+=PI*2;

    return angle<PI/2 ? 0 : angle<PI ? 1 : angle<3*PI/2 ? 2 : 3;
}

void Add()
{
    n++;

    double z;

    cin>>z;a[n].input();

    a[n].x/=z;
    a[n].y/=z;

    POINT v=a[n]-T1;

    v.norm();

    s[getID(v)].insert(v);

    //cout<<atan2(v.y,v.x)<<' '<<atan2(-v.y,-v.x)<<' '<<getID(v)<<'\n';
}

set<POINT>::iterator Find(POINT p,int id)
{
    auto it=s[id].lower_bound(p);

    if(it!=s[id].begin()) it--;

    for(int i=0;i<3;i++)
    {
        if(it==s[id].end()) break;

        if(*it==p) return it;

        it++;
    }

    return s[id].end();
}

void Erase()
{
    int id;

    cin>>id;

    POINT v=a[id]-T1;

    v.norm();

    int ID=getID(v);

    auto it=Find(v,ID);

    if(it!=s[ID].end()) s[ID].erase(it);
}

int check()
{
    if(Find(POINT(),0)!=s[0].end()) return 1;

    for(int id=0;id<2;id++)
    {
        int newid=id+2;

        for(POINT p:s[id])
        {
            if(Find(POINT()-p,newid)!=s[newid].end()) return 2;
        }
    }

    for(int i=0;i<4;i++) for(int j=i+1;j<4;j++) for(int k=j+1;k<4;k++)
    {
        if(s[i].empty()||s[j].empty()||s[k].empty()) continue;

        for(int ibest=0;ibest<2;ibest++) for(int jbest=0;jbest<2;jbest++) for(int kbest=0;kbest<2;kbest++)
        {
            POINT pi = ibest==1 ? *s[i].rbegin() : *s[i].begin();
            POINT pj = jbest==1 ? *s[j].rbegin() : *s[j].begin();
            POINT pk = kbest==1 ? *s[k].rbegin() : *s[k].begin();

            if(pi+pj+pk==POINT(0,0)) return 3;
        }
    }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    nhap();

    while(q--)
    {
        char type;

        cin>>type;

        if(type=='A') Add();
        else Erase();

        cout<<check()<<'\n';
    }

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...