# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
3414 | wookayin | Divide into triangle (kriii1_D) | C++98 | 0 ms | 1204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
struct point
{
int x,y;
int ind;
int use;
};
int n;
vector<point> dat;
long long ccw(const point &a, const point &b, const point &c)
{
long long ax = b.x - a.x, ay = b.y - a.y;
long long bx = c.x - a.x, by = c.y - a.y;
return ax*by - bx*ay;
}
int main()
{
scanf("%d",&n);
for(int i = 0; i < 3*n;i ++) {
int a,b;
scanf("%d%d",&a,&b);
point p;
p.x = a;
p.y = b;
p.ind = i+1;
p.use = 0;
dat.push_back(p);
}
for(int i = 0;i < n; i++) {
point *p1 = NULL, *p2 = NULL, *p3 = NULL;
for(int j = 0; j < 3*n; j++) {
if (dat[j].use) continue;
if (p1 == NULL || p1->x > dat[j].x || (p1->x == dat[j].x && p1->y > dat[j].y))
{
p1 = &dat[j];
}
}
p1->use = 1;
for(int j = 0; j < 3*n; j++) {
if (dat[j].use) continue;
if (p2 == NULL || ccw(*p1, *p2, dat[j]) > 0)
{
p2 = &dat[j];
}
}
p2->use = 1;
for(int j = 0; j < 3*n; j++) {
if (dat[j].use) continue;
if (p3 == NULL || ccw(*p1, *p2, dat[j]) > 0)
{
p3 = &dat[j];
}
}
p3->use = 1;
printf("%d %d %d\n",p1->ind, p2->ind, p3->ind);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |