代码

#define L2
// measurement probe for noi17f: dumps per-testcase  (2000 + min(h/4,24000)) pages
// where h = |hull(P)|  (default) or, with -DL2, h = |hull(P \ hull(P))| (second layer).
// The judge reports Memory (KiB) = 4*(baseline + pages), baseline ~ 400 pages.
#include <sys/auxv.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long u64;
typedef long long ll;
struct DI { u64 abi; const char* in; u64 insz; char* out; u64 outlim; u64 outsz; char* err;
            u64 errlim; u64 errsz; const char* IB; u64 IBlim; char* OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
static const int MAXN = 100005;
static int n, m;
static int px[MAXN], py[MAXN], ordr[MAXN];
static unsigned char used[MAXN];
static int hull[MAXN];
static inline ll cr(int a, int b, int c) {
    return (ll)(px[b]-px[a])*(ll)(py[c]-py[a]) - (ll)(py[b]-py[a])*(ll)(px[c]-px[a]);
}
static char *ip;
static inline int rd() {
    while ((unsigned char)*ip <= ' ') ip++;
    int sgn = 1; if (*ip=='-') { sgn=-1; ip++; }
    int v = 0; while ((unsigned char)*ip >= '0') { v = v*10 + (*ip-'0'); ip++; }
    return v*sgn;
}
static int buildHull() {
    int hn = 0;
    for (int t = 0; t < n; t++) { int id = ordr[t]; if (used[id]) continue;
        while (hn >= 2 && cr(hull[hn-2], hull[hn-1], id) <= 0) hn--;
        hull[hn++] = id; }
    if (hn >= 2) { int low = hn;
        for (int t = n-2; t >= 0; t--) { int id = ordr[t]; if (used[id]) continue;
            while (hn >= low+1 && cr(hull[hn-2], hull[hn-1], id) <= 0) hn--;
            hull[hn++] = id; }
        hn--; }
    return hn;
}
static char pad[110 << 20];
int main() {
    DI* di = (DI*)getauxval(0x6b637564);
    if (!di) return 0;
    ip = (char*)di->in;
    n = rd(); m = rd();
    for (int i = 0; i < n; i++) { px[i] = rd(); py[i] = rd(); ordr[i] = i; }
    sort(ordr, ordr+n, [](int a, int b){ return px[a] != px[b] ? px[a] < px[b] : py[a] < py[b]; });
    int h = buildHull();
#ifdef L2
    for (int i = 0; i < h; i++) used[hull[i]] = 1;
    int l2 = buildHull();
    u64 v = 2000 + (u64)min(l2 >> 2, 24000);
#else
    u64 v = 2000 + (u64)min(h >> 2, 24000);
#endif
    volatile char* p = pad;
    for (u64 i = 0; i < v; i++) p[i*4096] = 1;
    return 0;
}

评测结果