rendered paste body#include <stdio.h>#include <stdlib.h>struct str{ int x; int y; int nr; int kto;}*wstr;int n;int wynik[100000];struct str *wsk_tab[100000], *maly;void wczytanie(void);void minimalny(void);void dnc(int min, int);int comp(const void *a, const void *b);int main(){int i; wczytanie(); minimalny(); dnc(0, 2*n); for(i=1; i<=n; i++) printf("%d\n", wynik[i]); return 0;}/*-----------------------------------------*/void wczytanie(void){ int i, k; scanf("%d", &n); (wstr)=malloc(2*n*sizeof(struct str)); for(i=0,k=1; i<2*n;i++) { scanf("%d", &(wstr+i)->x); scanf("%d", &(wstr+i)->y); if(i<n) { /*pogromcy*/ (wstr+i)->nr=i+1; (wstr+i)->kto=1; wsk_tab[i]=(wstr+i); } else { /*duchy*/ (wstr+i)->nr=k; (wstr+i)->kto=0; wsk_tab[i]=(wstr+i); k++; } }}/*-------------------------------------------*/void minimalny(void){ int i,z=0; for(i=0; i<2*n-1;i++) { if(wsk_tab[i]->y == wsk_tab[z]->y) { if(wsk_tab[i]->x < wsk_tab[z]->x) z=i; } else if(wsk_tab[i]->y < wsk_tab[z]->y) z=i; } wsk_tab[0]=wstr+z; wsk_tab[z]=wstr;}/*-------------------------------------------*/int comp(const void *a, const void *b){ struct str *A= *(struct str**)a; struct str *B= *(struct str**)b; return((A->x - maly->x)*(B->y -maly->y)-(B->x - maly->x)*(A->y - maly->y));}/*-------------------------------------------*/void dnc(int min, int rozmiar){ int i; int pogromcy=0, duchy=0; if(rozmiar==2) { if(wsk_tab[0]->kto==1) { wynik[wsk_tab[0]->nr]=wsk_tab[1]->nr; } else if(wsk_tab[0]->kto==0) { wynik[wsk_tab[1]->nr]=wsk_tab[0]->nr; } } else { maly=wsk_tab[min]; qsort(wsk_tab+1, rozmiar-1, sizeof(struct str *), comp); for(i=0;i<=rozmiar;i++) { if((pogromcy>0) && (pogromcy==duchy)) { if(wsk_tab[0]->kto==1) { wynik[wsk_tab[0]->nr]=wsk_tab[2*duchy-1]->nr; break; } else if(wsk_tab[0]->kto==0) { wynik[wsk_tab[2*duchy-1]->nr]=wsk_tab[0]->nr; break; } } if(wsk_tab[i]->kto==1) pogromcy++; else if (wsk_tab[i]->kto==0) duchy++; } if((i-2)>=2) { dnc(min+1,i-2); } if((rozmiar-i)>=2) { dnc(min+i,rozmiar-i); }}}