Submission #366169

#	Time	Username	Problem	Language	Result	Execution time	Memory
366169		sealnot123	Relay (COI16_relay)	C++14	100 / 100	736 ms	35052 KiB

relay

/*
 * Task : https://oj.uz/problem/view/COI16_relay
 * (N+M)*log(N+M) attempt
 *
 * @Author AquaBlaze
 *
 * Keqing is a good girl :3
 * Ganyu is so cuuuuuute >_<
 * Nephren best loli x)
 */

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a),i2=(b); i<=i2; ++i)
#define ROF(i, a, b) for(int i=(a),i2=(b); i>=i2; --i)
#define all(a) (a).begin(),(a).end()
#define make_unique(x) sort(all((x))), (x).erase(unique(all((x))), (x).end())
#define TESTCASE int t; cin >> t; while(t--)

using namespace std;

typedef long long i64;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 100005;

map<pll, bool> relay, mark;
pll A[N], B[N];
pll hull[N<<1], Stack[N<<1];
bool seen[N<<1];
int hsize;

pll operator + (const pll A, const pll B){
    return pll(A.x+B.x, A.y+B.y);
}
pll operator - (const pll A, const pll B){
    return pll(A.x-B.x, A.y-B.y);
}

i64 cross(pll A, pll B){
    return A.y*B.x-A.x*B.y;
}
i64 dist(pll A, pll B){
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

void make_hull(){
    //printf("#### make hull ####\n");
    sort(hull+1,hull+1+hsize);
    //printf("size before sort = %d\n",hsize);
    hsize = unique(hull+1,hull+1+hsize)-hull-1;
    //printf("size after sort = %d\n",hsize);
    function<bool(pll,pll)> cmp = [&](pll a, pll b)->bool{
        i64 res = cross(a-hull[1],b-hull[1]);
        if(res == 0) return dist(a,hull[1])<dist(b,hull[1]);
        else return res<0;
    };
    sort(hull+2,hull+1+hsize, cmp);
    // reverse the final part
    int last = hsize;
    while(cross(hull[hsize]-hull[1],hull[last-1]-hull[hsize])==0)
        --last;
    reverse(hull+last, hull+1+hsize);
    // start making hull
    int top = 2;
    FOR(i, 1, 2) Stack[i] = hull[i];
    FOR(i, 3, hsize){
        while(top>1 && cross(Stack[top]-Stack[top-1],hull[i]-Stack[top])>0){
            --top;
        }
        if(relay[hull[i]]){
            while(top>1 && cross(Stack[top]-Stack[top-1],hull[i]-Stack[top])==0){
                --top;
            }
        }
        Stack[++top] = hull[i];
    }
    hsize = top;
    FOR(i, 1, hsize){
        hull[i] = Stack[i];
        seen[i] = mark[hull[i]];
    }
}

bool signal(pll p){
    // check if it's inside
    if(p.x < hull[1].x) return false;
    i64 x;
    x = cross(hull[2]-hull[1],p-hull[1]);
    if(x > 0) return false;
    if(x == 0) return dist(hull[1],hull[2])>=dist(hull[1],p);
    x = cross(hull[hsize]-hull[1],p-hull[1]);
    if(x < 0) return false;
    if(x == 0) return dist(hull[1],hull[hsize])>=dist(hull[1],p);
    /*
    // in-between case
    FOR(i, 2, hsize){
        if(cross(hull[i]-hull[1],p-hull[1])==0)
            return dist(hull[1],hull[i])>=dist(hull[1],p);
    }
    */
    // binary search part
    int l = 2, r = hsize-1;
    while(l < r){
        int m = (l+r+1)>>1;
        if(cross(hull[m]-hull[1], p-hull[1])<=0) l = m;
        else r = m-1;
    }
    return cross(hull[l+1]-hull[l],p-hull[l])<=0;
}

void solve(){
    /*
    int x[] = {0,1,1,2,3,5};
    int y = unique(x+1,x+6)-x-1;
    FOR(i,1,y) printf("%d ",x[i]);
    printf("%d",y);
    */
    int n, m;
    scanf("%d",&n);
    FOR(i, 1, n){
        scanf("%lld %lld",&A[i].x,&A[i].y);
        relay[A[i]] = true;
    }
    scanf("%d",&m);
    FOR(i, 1, m) scanf("%lld %lld",&B[i].x,&B[i].y);
    mark[A[1]] = true;
    FOR(i, 1, m) hull[i]=B[i];
    hsize = m;
    hull[++hsize] = A[1];
    make_hull();
    
    /*
    printf("FIRST hull:\n");
    FOR(i, 1, hsize){
        printf("(%lld, %lld) ",hull[i].x,hull[i].y);
        if(mark[hull[i]]) printf("*");
        puts("");
    }
    */

    FOR(i, 2, n){
        if(signal(A[i])) mark[A[i]]=true;
    }
    FOR(i, 1, hsize){
        if(hull[i] == A[1]){
            int pv = i-1;
            if(pv==0) pv = hsize;
            int nx = i+1;
            if(nx==hsize+1) nx = 1;
            FOR(j, 2, n){
                bool a = (cross(hull[pv]-hull[i],A[j]-hull[i])>0);
                bool b = (cross(hull[nx]-hull[i],A[j]-hull[i])<0);
                if(a&&b) continue;
                mark[A[j]] = true;
            }
            break;
        }
    }
    FOR(i, 2, n){
        if(mark[A[i]]) hull[++hsize] = A[i];
    }
    make_hull();

    /*
    printf("SECOND hull:\n");
    FOR(i, 1, hsize){
        printf("(%lld, %lld) ",hull[i].x,hull[i].y);
        if(mark[hull[i]]) printf("*");
        puts("");
    }
    */

    FOR(i, 2, n){
        if(mark[A[i]]) continue;
        if(signal(A[i])) mark[A[i]]=true;
    }
    bool found = false;
    FOR(i, 1, hsize){
        int nx = i+1;
        if(nx == hsize+1) nx = 1;
        bool a = seen[i];
        bool b = seen[nx];
        if(a^b){
            found = true;
            FOR(j, 2, n){
                if(mark[A[j]]) continue;
                if(cross(hull[nx]-hull[i], A[j]-hull[i])>=0){
                    mark[A[j]] = true;
                }
            }
            FOR(j, 2, n){
                if(mark[A[j]]) continue;
                if(cross(hull[nx]-hull[i], A[j]-hull[i])>=0){
                    mark[A[j]] = true;
                }
            }
        }
    }
    if(!found){
        printf("%d",n-1);
        return ;
    }
    int ans = 0;
    FOR(i, 2, n){
        ans += mark[A[i]];
        //if(mark[A[i]]) printf("==(%lld %lld)\n",A[i].x,A[i].y);
    }
    printf("%d",ans);
}

int main(){
    solve();
	return 0;
}

Compilation message (stderr)

relay.cpp: In function 'void solve()':
relay.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
relay.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |         scanf("%lld %lld",&A[i].x,&A[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
relay.cpp:134:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |     FOR(i, 1, m) scanf("%lld %lld",&B[i].x,&B[i].y);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 43 / 43