oj.uz

Submission #366169

# Submission time Handle Problem Language Result Execution time Memory
366169 2021-02-13T12:13:53 Z sealnot123 Relay (COI16_relay) C++14
100 / 100
 736 ms 35052 KB 
/*
 * 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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 396 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 396 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 8 ms 1260 KB Output is correct
12 Correct 8 ms 1260 KB Output is correct
13 Correct 6 ms 1004 KB Output is correct
14 Correct 8 ms 1132 KB Output is correct
15 Correct 8 ms 1004 KB Output is correct
16 Correct 8 ms 1004 KB Output is correct
17 Correct 8 ms 1004 KB Output is correct
18 Correct 7 ms 1004 KB Output is correct
19 Correct 8 ms 1004 KB Output is correct
20 Correct 9 ms 1004 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 396 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 134 ms 15084 KB Output is correct
12 Correct 150 ms 17188 KB Output is correct
13 Correct 204 ms 17148 KB Output is correct
14 Correct 183 ms 17132 KB Output is correct
15 Correct 528 ms 16860 KB Output is correct
16 Correct 399 ms 16620 KB Output is correct
17 Correct 414 ms 16748 KB Output is correct
18 Correct 422 ms 16888 KB Output is correct
19 Correct 462 ms 16492 KB Output is correct
20 Correct 423 ms 16620 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 396 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 8 ms 1260 KB Output is correct
12 Correct 8 ms 1260 KB Output is correct
13 Correct 6 ms 1004 KB Output is correct
14 Correct 8 ms 1132 KB Output is correct
15 Correct 8 ms 1004 KB Output is correct
16 Correct 8 ms 1004 KB Output is correct
17 Correct 8 ms 1004 KB Output is correct
18 Correct 7 ms 1004 KB Output is correct
19 Correct 8 ms 1004 KB Output is correct
20 Correct 9 ms 1004 KB Output is correct
21 Correct 134 ms 15084 KB Output is correct
22 Correct 150 ms 17188 KB Output is correct
23 Correct 204 ms 17148 KB Output is correct
24 Correct 183 ms 17132 KB Output is correct
25 Correct 528 ms 16860 KB Output is correct
26 Correct 399 ms 16620 KB Output is correct
27 Correct 414 ms 16748 KB Output is correct
28 Correct 422 ms 16888 KB Output is correct
29 Correct 462 ms 16492 KB Output is correct
30 Correct 423 ms 16620 KB Output is correct
31 Correct 359 ms 35052 KB Output is correct
32 Correct 374 ms 34984 KB Output is correct
33 Correct 246 ms 27628 KB Output is correct
34 Correct 296 ms 27504 KB Output is correct
35 Correct 736 ms 25836 KB Output is correct
36 Correct 732 ms 26280 KB Output is correct
37 Correct 609 ms 25068 KB Output is correct
38 Correct 662 ms 25596 KB Output is correct
39 Correct 572 ms 24916 KB Output is correct
40 Correct 581 ms 24812 KB Output is correct