Submission #153835

#	Time	Username	Problem	Language	Result	Execution time	Memory
153835		nicolaalexandra	Tri (CEOI09_tri)	C++14	100 / 100	973 ms	28160 KiB

tri

#include <iostream>
#include <vector>
#include <algorithm>
#define DIM 100010
#define x first
#define y second

using namespace std;

pair<int,int> points[DIM];
vector < pair<int,int> > aint[4*DIM],d;
int n,q,i,ok;
pair<int,int> a,b;

inline long long get_det (pair<int,int> a, pair<int,int> b, pair<int,int> c){
    return 1LL*(b.x-a.x)*(c.y-a.y) - 1LL*(b.y-a.y)*(c.x-a.x);
}
inline int cmp (pair<int,int> a, pair<int,int> b){
    return get_det (make_pair(0,0),a,b) < 0;
}
inline int binarySearch_aint (vector< pair<int,int> > v, pair<int,int> a, pair<int,int> b){
    /// daca gasesc vreun punct situat sub dreapta a,b
    int st = 0, dr = v.size()-2;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (get_det(a,b,v[mid]) >= get_det(a,b,v[mid+1]))
            st = mid+1;
        else dr = mid-1;
    }
    if (get_det(a,b,v[st]) < 0)
        return 1;
    return 0;
}
inline int binarySearch (pair<int,int> v[], pair<int,int> point){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (get_det(make_pair(0,0),point,v[mid]) <= 0)
            dr = mid-1;
        else st = mid+1;
    }
    return st;
}
inline void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].push_back(points[st]);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    /// acum trebuie sa fac infasuratoarea convexa pt intervalul st dr
    aint[nod].push_back(points[st]);
    aint[nod].push_back(points[st+1]);
    for (int i=st+2;i<=dr;i++){
        while (aint[nod].size() >= 2 && get_det(aint[nod][aint[nod].size()-2],aint[nod][aint[nod].size()-1],points[i]) <= 0)
            aint[nod].pop_back();
        aint[nod].push_back(points[i]);
    }}
inline void query (int nod, int st, int dr, int x, int y){
    if (ok)
        return;
    if (x <= st && dr <= y){
        /// vreau sa vad daca am macar un punct sub latura triunghiului care nu are niciun punct in origine
        int l = 0, r = aint[nod].size()-2;
        while (l <= r){
            int m = (l+r)>>1;
            if (get_det(a,b,aint[nod][m]) >= get_det(a,b,aint[nod][m+1]))
                l = m+1;
            else r = m-1;
        }
        if (get_det(a,b,aint[nod][l]) < 0)
            ok = 1;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

int main (){
    //InParser fin ("tri3.in");
    //ofstream fout ("tri3.out");
    cin>>n>>q;
    for (i=1;i<=n;++i)
        cin>>points[i].x>>points[i].y;

    /// sortez punctele dupa unghi
    sort (points+1,points+n+1,cmp);
    build (1,1,n);
    for (;q--;){
        cin>>a.x>>a.y>>b.x>>b.y;
        if (get_det(make_pair(0,0),a,b) > 0)
            swap (a,b);
        /// trebuie sa gasesc intervalul de puncte care e cuprins intre cele doua laturi care pleaca din origine
        int poz1 = binarySearch(points,a);
        int poz2 = binarySearch(points,b);
        --poz2; /// cautarea imi da punctul imediat dupa
        if (poz1 <= poz2){
            ok = 0;
            query (1,1,n,poz1,poz2);
            (ok) ? (cout<<"Y\n") : (cout<<"N\n");
        } else cout<<"N\n";
    }


    return 0;
}

• Subtask 1: 100 / 100