Pagini recente » Cod sursa (job #1907976) | Cod sursa (job #3282048) | Cod sursa (job #2446983) | Cod sursa (job #2532874) | Cod sursa (job #1224514)
//
// 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;
}