Submission #3395

#	Time	Username	Problem	Language	Result	Execution time	Memory
3395		blmarket	Divide into triangle (kriii1_D)	C++98	1 / 1	4 ms	1688 KiB

D

#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 / 1