Cod sursa(job #2637700)

Utilizator marinaoprOprea Marina marinaopr Data 24 iulie 2020 12:12:50
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.63 kb
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#define pb push_back
const int maxn = 120000;
using namespace std;
vector<int> VECT;
double X[maxn],Y[maxn];
int N,VER[maxn],nrcoliniare,coliniare[maxn],nextTarget,curent,val,punct_initial;
bool sel[maxn];
 int distance( int a,int b,int c)
 {
     double xab=X[a]-X[b];
     double xac=X[a]-X[c];
     double yab=Y[a]-Y[b];
     double yac=Y[a]-Y[c];
     double d1=xab*xab+yab*yab;
     double d2=xac*xac+yac*yac;
     if(d1==d2) return 0;
     else if(d1>d2) return 1;
     return -1;
      }

  int crossProduct(int a,int b,int c) {
   double x1=X[a]-X[b];
   double x2=X[a]-X[c];
   double y1=Y[a]-Y[b];
   double y2=Y[a]-Y[c];
   double d=x1*y2-x2*y1;
   if(d<0) return -1;
   if(d==0) return 0;
   else return 1;

  }

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d\n",&N);
	X[0] = 1000000000;Y[0] = 1000000000;
	for(int i = 1;i <= N; ++i)
		scanf("%lf %lf\n",&X[i],&Y[i]);

	int move = 1;
    for(int i = 1;i <= N; ++i)
		if (X[i] < X[punct_initial]) punct_initial = i;
		sel[punct_initial]=1;
	curent = punct_initial;
	VECT.pb(punct_initial);
    while(1)
    {
         nextTarget = 1;
         while(sel[nextTarget]==1) nextTarget++;
            for (int i= 2; i <=N; i++) {
                if (i == curent) {
                    continue;
                }
                 val = crossProduct(curent, nextTarget, i);
                //if val > 0 it means points[i] is on left of current -> nextTarget. Make him the nextTarget.
                if (val > 0) {
                    nextTarget = i;
                    //reset collinear points because we now have a new nextTarget.
                   // collinearPoints = new ArrayList<>();
                   nrcoliniare=0;
                } else if (val == 0) { //if val is 0 then collinear current, nextTarget and points[i] are collinear.
                    //if its collinear point then pick the further one but add closer one to list of collinear points.
                    if (distance(curent, nextTarget, i) < 0) {
                            nrcoliniare++;
                            coliniare[nrcoliniare]=nextTarget;
                        //collinearPoints.add(nextTarget);
                        nextTarget = i;
                    } else { //just add points[i] to collinearPoints list. If nextTarget indeed is the next point on
                        //convex then all points in collinear points will be also on boundary.
                       // collinearPoints.add(points[i]);
                             nrcoliniare++;
                            coliniare[nrcoliniare]=i;
                    }
                }
                //else if val < 0 then nothing to do since points[i] is on right side of current -> nextTarget.
            }

            //add all points in collinearPoints to result.
            for (int t=1;t<=nrcoliniare;t++) {
                VECT.pb(coliniare[t]);sel[coliniare[t]]=1;
            }
            //if nextTarget is same as start it means we have formed an envelope and its done.
            if (nextTarget == punct_initial) {
                break;
            }
            //add nextTarget to result and set current to nextTarget.
           // result.add(nextTarget);
           VECT.pb(nextTarget);
           sel[nextTarget]=1;
            curent = nextTarget;
        }
        	reverse(VECT.begin(),VECT.end());

	printf("%d\n",VECT.size());

	for(unsigned int i = 0;i < VECT.size(); ++i)

		printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);

	return 0;
    }