Submission #3633

#TimeUsernameProblemLanguageResultExecution timeMemory
3633eldkqmfhf123Divide into triangle (kriii1_D)C++98
0 / 1
0 ms8036 KiB
#include<iostream> #include<math.h> #include<algorithm> #define oo 0x7fffffff using namespace std; double Dist[901][901]; double dist(int ax,int ay, int bx, int by) { double a = (bx-ax)*(bx-ax); double b = (by-ay)*(by-ay); return sqrt(a+b); } int Data[901][2]; int visit[901]; int main() { int n; cin >> n; int i,j; for(i=0;i<3*n;i++) cin >> Data[i][0] >> Data[i][1]; n *= 3; for(i=0;i<n;i++) { for(j=0;j<n;j++) { Dist[i][j] = dist(Data[i][0],Data[i][1],Data[j][0],Data[j][1]); } } for(int t=0;t<n/3;t++) { for(i=0;i<n;i++) { if(visit[i])continue; double MIN = oo; int MINJ; for(j=0;j<n;j++) { if(visit[j])continue; if(i==j)continue; if(MIN > Dist[i][j]) { MIN = Dist[i][j]; MINJ = j; } } double MIN2 = oo; int MINJ2; for(j=0;j<n;j++) { if(visit[j])continue; if(i==j || MINJ == j)continue; if(MIN2 > Dist[i][j]) { MIN2 = Dist[i][j]; MINJ2 = j; } } int tmp[4]; tmp[0]=i+1; tmp[1]=MINJ+1; tmp[2]=MINJ2+1; for(int q=0;q<3;q++) cout << tmp[q] << " "; cout << endl; sort(tmp,tmp+3); visit[i]=1; visit[MINJ]=1; visit[MINJ2]=1; break; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...