Cod sursa(job #1224506)

Utilizator alex23alexandru andronache alex23 Data 31 august 2014 11:21:52
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 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>

//#define M_PI 3.1415926535

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;

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;
        }
    }
    
    polygon.push_back(min);
    points[index].verified = true;
    double last = 0;
    int current = 0;
    while (current == 0 || (polygon[current].x != polygon[0].x || polygon[current].y != polygon[0].y))
    {
        int new_index = -1;
        double new_unghi = 100000;
        for (int i = 0; i < N; ++i)
        {
            //if (!points[i].verified)
            {
                double unghi = atan2((points[i].x - polygon[current].x), (points[i].y - polygon[current].y));
                if (unghi < 0) unghi += 2* M_PI;
                unghi -= last;
                if (unghi < 0) unghi += 2 * M_PI;
                if (new_unghi > unghi && (polygon[current].x != points[i].x || polygon[current].y != points[i].y))
                {
                    new_unghi = unghi;
                    new_index = i;
                }
            }
        }
        if (new_index != -1)
        {
            last = atan2(-(polygon[current].x - points[new_index].x),-(polygon[current].y - points[new_index].y));
            if (last < 0) last += 2 * M_PI;
            current++;
            polygon.push_back(points[new_index]);
            points[new_index].verified = true;
        }
        else
        {
            current++;
            polygon.push_back(polygon[0]);
        }
    }
    
    reverse(polygon.begin(), polygon.end());
    fprintf(g, "%d\n", polygon.size() - 1);
    for (int i = 1; i < polygon.size(); ++i)
    {
        fprintf(g, "%.6f %.6f\n", polygon[i].x, polygon[i].y);
    }
    
    
    fclose(f);
    fclose(g);
    return 0;
}