oj.uz

Submission #366161

# Submission time Handle Problem Language Result Execution time Memory
366161 2021-02-13T11:48:50 Z sealnot123 Relay (COI16_relay) C++14
37 / 100
 2000 ms 17132 KB 
/*
 * Task : https://oj.uz/problem/view/COI16_relay
 * (N+M)^2 attempt
 *
 * @Author AquaBlaze
 *
 * Keqing is a good girl :3
 * Nephren is the 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 on some extended edges
    // check if it's inside
    FOR(i, 1, hsize){
        int nxt = i+1;
        if(nxt>hsize) nxt = 1;
        if(cross(hull[nxt]-hull[i],p-hull[i])==0){
            return (mark[hull[i]]|mark[hull[nxt]]);
        }
        if(cross(hull[nxt]-hull[i],p-hull[i])>0){
            return false;
        }
    }
    return true;
}

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:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
relay.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         scanf("%lld %lld",&A[i].x,&A[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
relay.cpp:122:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |     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 2 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 364 KB Output is correct
5 Correct 1 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 2 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 2 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 364 KB Output is correct
5 Correct 1 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 2 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 27 ms 1452 KB Output is correct
12 Correct 25 ms 1388 KB Output is correct
13 Correct 12 ms 1152 KB Output is correct
14 Correct 16 ms 1232 KB Output is correct
15 Correct 16 ms 1132 KB Output is correct
16 Correct 14 ms 1132 KB Output is correct
17 Correct 14 ms 1132 KB Output is correct
18 Correct 14 ms 1132 KB Output is correct
19 Correct 18 ms 1132 KB Output is correct
20 Correct 23 ms 1260 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 364 KB Output is correct
5 Correct 1 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 2 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 2068 ms 17132 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 364 KB Output is correct
5 Correct 1 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 2 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 27 ms 1452 KB Output is correct
12 Correct 25 ms 1388 KB Output is correct
13 Correct 12 ms 1152 KB Output is correct
14 Correct 16 ms 1232 KB Output is correct
15 Correct 16 ms 1132 KB Output is correct
16 Correct 14 ms 1132 KB Output is correct
17 Correct 14 ms 1132 KB Output is correct
18 Correct 14 ms 1132 KB Output is correct
19 Correct 18 ms 1132 KB Output is correct
20 Correct 23 ms 1260 KB Output is correct
21 Execution timed out 2068 ms 17132 KB Time limit exceeded
22 Halted 0 ms 0 KB -