# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
3394 | cki86201 | Divide into triangle (kriii1_D) | C++98 | 0 ms | 1324 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<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
struct point{
point(){}
point(int x,int y):x(x),y(y){}
int x,y;
bool operator<(const point &l)const{return x!=l.x?x<l.x:y<l.y;}
}p[920];
int N;
bool check[920];
int o[920];
bool comp(const int &a,const int &b)
{
return p[a]<p[b];
}
void solve(int x)
{
int i,p1=0,p2=0;
check[x]=1;
double a1,a2;
for(i=1;i<=3*N;i++){
if(check[i])continue;
if(p1==0 && p2==0){a1=atan2(p[i].y-p[x].y, p[i].x-p[x].x);p1=i;continue;}
if(p2==0){a2=atan2(p[i].y-p[x].y, p[i].x-p[x].x);p2=i;continue;}
double f = atan2(p[i].y-p[x].y, p[i].x-p[x].x);
if(f<a1){a2=a1;p2=p1;a1=f;p1=i;continue;}
if(f<a2){a2=f;p2=i;continue;}
}
check[p1]=check[p2]=1;
printf("%d %d %d\n",x,p1,p2);
}
int main()
{
int i;
scanf("%d",&N);
for(i=1;i<=3*N;i++){
scanf("%d%d",&p[i].x,&p[i].y);
}
for(i=1;i<=3*N;i++)o[i]=i;
sort(o+1,o+1+3*N);
for(i=1;i<=3*N;i++){
if(check[o[i]])continue;
solve(o[i]);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |