Submission #322308

#	Time	Username	Problem	Language	Result	Execution time	Memory
322308		lohacho	공룡 발자국 (KOI18_footprint)	C++14	100 / 100	115 ms	748 KiB

footprint

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
LL ccw(LL a, LL b, LL c, LL d){
    LL rv = a * d - b * c;
    return rv ? rv > 0 ? 1 : -1 : 0;
}
 
LL N;
struct data{
    LL x, y, mx, my;
    bool operator<(const data&r)const{
        return ccw(mx, my, r.mx, r.my) == 1;
    }
}arr[3004];
LL d[3004][3], from[3004][3];
 
void out(LL A, LL B, LL dep){
    if(A == 1){
        printf("%lld\n%lld %lld\n", dep, arr[A].x, arr[A].y);
        return;
    }
    out(from[A][B], 1 - B, dep + 1);
    printf("%lld %lld\n", arr[A].x, arr[A].y);
}
 
int main(){
    scanf("%lld", &N);
    LL low = (LL)1e9, num;
    for(LL i = 1; i <= N; ++i){
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
        if(arr[i].y < low){
            low = arr[i].y, num = i;
        }
    }
    swap(arr[1], arr[num]);
    for(LL i = 1; i <= N; ++i){
        arr[i].mx = arr[i].x - arr[1].x;
        arr[i].my = arr[i].y - arr[1].y;
    }
    sort(arr + 2, arr + N + 1);
    for(LL i = 2; i <= N; ++i){
        d[i][1] = from[i][1] = 1;
    }
    for(LL i = 3; i <= N; ++i){
        for(LL k = 0; k < 2; ++k){
            for(LL j = 2; j < i; ++j){
                if(ccw(arr[i].mx, arr[i].my, arr[j].mx, arr[j].my) == 0){
                    continue;
                }
                if(from[j][1 - k] && ccw(arr[i].x - arr[from[j][1 - k]].x, arr[i].y - arr[from[j][1 - k]].y,
                                         arr[j].x - arr[from[j][1 - k]].x, arr[j].y - arr[from[j][1 - k]].y) == k - (k == 0)){
                    if(d[j][1 - k] + 1 > d[i][k] || !from[i][k] || (d[j][1 - k] + 1 == d[i][k] &&
                        ccw(arr[from[i][k]].x - arr[i].x, arr[from[i][k]].y - arr[i].y,
                            arr[j].x - arr[i].x, arr[j].y - arr[i].y) != k - (k == 0))){
                        d[i][k] = d[j][1 - k] + 1;
                        from[i][k] = j;
                    }
                }
            }
        }
    }
    LL pos, big = -1;
    for(LL i = 2; i <= N; ++i){
        if(d[i][1] > big){
            big = d[i][1], pos = i;
        }
    }
    if(big < 3){
        puts("0"); return 0;
    }
    out(pos, 1, 1);
    return 0;
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
footprint.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%lld %lld", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
footprint.cpp:32:23: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |     LL low = (LL)1e9, num;
      |                       ^~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45