Pagini recente » Cod sursa (job #2567650) | Cod sursa (job #1192139) | Cod sursa (job #13287) | Cod sursa (job #1166135) | Cod sursa (job #1224506)
//
// 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;
}