Cod sursa(job #1224514)

Utilizator alex23alexandru andronache alex23 Data 31 august 2014 11:46:04
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
//
//  main.cpp
//  aa
//
//  Created by Alexandru Andronache on 8/23/14.
//  Copyright (c) 2014 Alexandru Andronache. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

struct point
{
    point(float i, float j)
    {
        x = i;
        y = j;
        verified = false;
    }
    float x;
    float y;
    bool verified;
};

using namespace std;

FILE *f = fopen("infasuratoare.in", "r");
FILE *g = fopen("infasuratoare.out", "w");

int N;

vector<point> points;
//vector<point> polygon;
vector<int> polygon;

int main(int argc, const char * argv[])
{
    fscanf(f, "%d", &N);
    for (int i = 0; i < N; ++i)
    {
        float p1, p2;
        fscanf(f, "%f", &p1);
        fscanf(f, "%f", &p2);
        points.push_back(point(p1, p2));
    }
    
    point min = points[0];
    int index = 0;
    for (int i = 1; i < N; ++i)
    {
        if (min.x > points[i].x)
        {
            min = points[i];
            index = i;
        }
        else if (min.x == points[i].x && min.y > points[i].y)
        {
            min = points[i];
            index = i;
        }
    }
    
    double last = 0;
    int current = index;
    int first_time = 0;
    while (first_time == 0 || (points[current].x != points[polygon[0]].x || points[current].y != points[polygon[0]].y))
    {
        first_time = 1;
        polygon.push_back(current);
        int new_index = current;
        double new_unghi = 100000;
        for (int i = 0; i < N; ++i)
        {
            if (!points[i].verified && i != current)
            {
                double unghi = atan2((points[i].x - points[current].x), (points[i].y - points[current].y));
                if (unghi < 0) unghi += 2* M_PI;
                unghi -= last;
                if (unghi < 0) unghi += 2 * M_PI;
                if (new_unghi > unghi)
                {
                    new_unghi = unghi;
                    new_index = i;
                }
            }
        }
        
        last = atan2(-(points[current].x - points[new_index].x),-(points[current].y - points[new_index].y));
        if (last < 0) last += 2 * M_PI;
        
        current = new_index;
        points[current].verified = true;
    }
    
    reverse(polygon.begin(), polygon.end());
    fprintf(g, "%d\n", polygon.size());
    for (int i = 0; i < polygon.size(); ++i)
    {
        fprintf(g, "%.6f %.6f\n", points[polygon[i]].x, points[polygon[i]].y);
    }
    
    
    fclose(f);
    fclose(g);
    return 0;
}