include iostream include vector include time include glut using namesp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>
#include <time.h>
#include "glut.h"
using namespace std;
struct point
{
double x, y;
};
int n;
point *points;
vector<int> hull;
const double eps = 0.000000000001;
double Area_Triangle(point a, point b, point c)
{
return 0.5 * (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y);
}
double dist(point p1, point p2)
{
return sqrt( (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y) );
}
bool less_of_ccw(point p1, point p2)
{
if ( Area_Triangle(points[0], p1, p2) > eps ) return true;
if ( Area_Triangle(points[0], p2, p1) > eps ) return false;
return dist(points[0], p1) > dist(points[0], p2);
}
void sortVib()
{
int imin;
point temp;
for (int k = 1; k < n-1; k++)
{
imin = k;
for (int i = k+1; i < n; i++)
if ( less_of_ccw(points[i], points[imin]) )
imin = i;
if (imin != k)
{
temp = points[k];
points[k] = points[imin];
points[imin] = temp;
}
}
}
void Graham()
{
int ifirst = 0, i;
for (i = 1; i < n; i++)
if (points[i].x < points[ifirst].x || (points[i].x == points[ifirst].x && points[i].y < points[ifirst].y)) ifirst = i;
point temp = points[0];
points[0] = points[ifirst];
points[ifirst] = temp;
sortVib();
hull.push_back(0);
hull.push_back(1);
i = 2;
int end_hull = 1;
while (i < n)
{
if (Area_Triangle(points[end_hull-1], points[end_hull], points[i]) > eps)
{
hull.push_back(i);
i++;
end_hull++;
}
else
{
hull.pop_back();
end_hull--;
}
}
}