bzoj1007: [HNOI2008]水平可见直线

import os
import sys
import re
from pydatagen import *

gen = sys.argv[1]
mycode = sys.argv[2]
std = sys.argv[3]
count = int(sys.argv[4])
gpp_invoke = '"C:\\Program Files (x86)\\Dev-Cpp\\MinGW64\\bin\\g++" %s -o %s'

# Pre-run compilation

printf('$ Compiling...\r')
mycode_e = re.sub('\\.cpp$', '.exe', mycode)
std_e = re.sub('\\.cpp$', '.exe', std)
if not os.path.exists(mycode_e):
    os.system(gpp_invoke % (mycode, mycode_e))
if not os.path.exists(std_e):
    os.system(gpp_invoke % (std, std_e))
printf('$ Compiling... OK\n')

# Execution and judging

same_count = 0

for i in range(0, count):
    printf('$ Checking round #%s: Generating data...%s\r' % (str(i + 1), ' ' * 16))
    os.system('python %s > __input__.txt' % gen)
    printf('$ Checking round #%s: Running "%s"...%s\r' % (str(i + 1), mycode, ' ' * 16))
    os.system('cat __input__.txt | %s > __out1__.txt' % mycode_e)
    printf('$ Checking round #%s: Running "%s"...%s\r' % (str(i + 1), std, ' ' * 16))
    os.system('cat __input__.txt | %s > __out2__.txt' % std_e)
    printf('$ Checking round #%s: Judging...%s\r' % (str(i + 1), ' ' * 16))
    f1 = open('__out1__.txt', 'r', encoding='utf-8')
    f2 = open('__out2__.txt', 'r', encoding='utf-8')
    str1 = f1.read().replace(r'[ \t\r\n]', '')
    str2 = f2.read().replace(r'[ \t\r\n]', '')
    f1.close()
    f2.close()
    same = str1 == str2
    if same:
        printf('$ Checking round #%s: OK%s\r' % (str(i + 1), ' ' * 16))
        same_count += 1
    else:
        printf('$ Checking round #%s: CORRECT%s\r' % (str(i + 1), ' ' * 16))
    printf('\n')

printf('$ Cleaning up...\r')
os.system('rm -f __input__.txt __out1__.txt __out2__.txt')
printf('$ Finished %d rounds, of which %d are correct\n' % (count, same_count))

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <map>

using namespace std;
const int maxn = 50100;

int             n, A[maxn], B[maxn];
int             seen[maxn];
map<int, int>   msort;
stack<int>      lres; // The result of lines
stack<double>   nodex; // X-axis values of vertexes

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Input data and meke sorts according to their k values.
    for (int i = 1; i <= n; i++) {
        seen[i] = 1;
        scanf("%d%d", &A[i], &B[i]);
        if (!msort[A[i]]) msort[A[i]] = i;
        else if (B[msort[A[i]]] < B[i]) msort[A[i]] = i;
    }
    // Preparing to calculate convex hull
    map<int, int>::iterator itert = msort.begin();
    lres.push(itert++->second);
    for (itert; itert != msort.end(); itert++) {
        int     l1 = itert->second; // The first line to deal with: the line to be added
        double  newx = 0.0;
        while (true) {
            int l2 = lres.top(); // The line to be checked
            newx = (double)(B[l2] - B[l1]) / (double)(A[l1] - A[l2]); // Calculate current X intersect
            if (nodex.empty()) break; // Now it should stop as it's reaching the #1 line.
            double lastx = nodex.top(); // Get last X-axis value intersection
            if (newx > lastx) break; // The new line shall live peacefully with the others
            // Then it might be removed, to make place for the new one...
            lres.pop();
            nodex.pop();
        }
        // Anyway it should be inserted.
        lres.push(l1);
        nodex.push(newx);
    }
    // We've got all, outputting
    msort.clear(); // This is a trick to avoid memory wasting
    while (!lres.empty()) {
        msort[lres.top()] = 1;
        lres.pop();
    }
    for (itert = msort.begin(); itert != msort.end(); itert++)
        printf("%d ", itert->first);
    return 0;
}

from pydatagen import *
n = randrange(1, 50000)
printf('%d\n' % n)
for i in range(0, n):
    a = randrange(-500000, 500000)
    b = randrange(-500000, 500000)
    printf('%d %d\n' % (a, b))
fclose()