oj.uz

Submission #366166

# Submission time Handle Problem Language Result Execution time Memory
366166 2021-02-13T12:11:05 Z sealnot123 Relay (COI16_relay) C++14
37 / 100
 2000 ms 15140 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:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
relay.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |         scanf("%lld %lld",&A[i].x,&A[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
relay.cpp:132:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |     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 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 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 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 25 ms 1260 KB Output is correct
12 Correct 24 ms 1260 KB Output is correct
13 Correct 14 ms 1004 KB Output is correct
14 Correct 14 ms 1152 KB Output is correct
15 Correct 21 ms 1004 KB Output is correct
16 Correct 14 ms 1004 KB Output is correct
17 Correct 16 ms 1004 KB Output is correct
18 Correct 12 ms 1004 KB Output is correct
19 Correct 16 ms 1004 KB Output is correct
20 Correct 18 ms 1004 KB Output is correct

Subtask #3
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 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Execution timed out 2058 ms 15140 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
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 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 25 ms 1260 KB Output is correct
12 Correct 24 ms 1260 KB Output is correct
13 Correct 14 ms 1004 KB Output is correct
14 Correct 14 ms 1152 KB Output is correct
15 Correct 21 ms 1004 KB Output is correct
16 Correct 14 ms 1004 KB Output is correct
17 Correct 16 ms 1004 KB Output is correct
18 Correct 12 ms 1004 KB Output is correct
19 Correct 16 ms 1004 KB Output is correct
20 Correct 18 ms 1004 KB Output is correct
21 Execution timed out 2058 ms 15140 KB Time limit exceeded
22 Halted 0 ms 0 KB -