oj.uz

Submission #3395

# Submission time Handle Problem Language Result Execution time Memory
3395 2013-08-31T05:25:20 Z blmarket Divide into triangle (kriii1_D) C++
1 / 1
 4 ms 1688 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int N;
pair<PII, int> V[1000];

bool cmp(const pair<PII, int> &aa, const pair<PII, int> &bb) {
    const PII &a = aa.first;
    const PII &b = bb.first;

    int xx1 = a.first - V[0].first.first;
    int yy1 = a.second - V[0].first.second;
    int xx2 = b.first - V[0].first.first;
    int yy2 = b.second - V[0].first.second;

    long long t1 = (long long)xx1 * yy2 - (long long)xx2 * yy1;
    return t1 < 0;
}

int main(void)
{
    cin >> N;
    N *= 3;
    for(int i=0;i<N;i++) {
        cin >> V[i].first.first >> V[i].first.second;
        V[i].second = i + 1;
    }

    sort(V, V+N);
    sort(V+1, V+N, cmp);

    for(int i=0;i<N;i++) {
        if(i && i % 3 == 0) cout << endl;
        cout << V[i].second << " ";
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1688 KB Output is correct
2 Correct 0 ms 1688 KB Output is correct
3 Correct 0 ms 1688 KB Output is correct
4 Correct 0 ms 1688 KB Output is correct
5 Correct 0 ms 1688 KB Output is correct
6 Correct 0 ms 1688 KB Output is correct
7 Correct 0 ms 1688 KB Output is correct
8 Correct 0 ms 1688 KB Output is correct
9 Correct 0 ms 1688 KB Output is correct
10 Correct 0 ms 1688 KB Output is correct
11 Correct 4 ms 1688 KB Output is correct
12 Correct 0 ms 1688 KB Output is correct
13 Correct 0 ms 1688 KB Output is correct
14 Correct 0 ms 1688 KB Output is correct
15 Correct 0 ms 1688 KB Output is correct
16 Correct 0 ms 1688 KB Output is correct
17 Correct 0 ms 1688 KB Output is correct
18 Correct 4 ms 1688 KB Output is correct
19 Correct 0 ms 1688 KB Output is correct
20 Correct 0 ms 1688 KB Output is correct