Pagini recente » Cod sursa (job #151409) | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3281056)
#include <fstream>
#include <algorithm>
using namespace std;
#define int long long
ifstream in("rubarba.in");
ofstream out("rubarba.out");
int n;
pair<int, int> v[100005];
pair<int, int> s[100005];
int det(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}
int dist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
int d = det(v[1], a, b);
if(d == 0)
{
return dist(v[1], a) < dist(v[1], b);
}
return d < 0;
}
signed main()
{
in>>n;
int poz = 1;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
if(v[i] < v[poz])
{
poz = i;
}
}
swap(v[1], v[poz]);
sort(v + 2, v + n + 1, cmp);
s[1] = v[1];
s[2] = v[2];
int head = 2;
for(int i = 3; i<=n; i++)
{
while(head >= 2 && det(s[head - 1], s[head], v[i]) > 0)
{
head--;
}
head++;
s[head] = v[i];
}
/*for(int i = 1; i<=head; i++)
{
out<<s[i].first<<" "<<s[i].second<<'\n';
}*/
if(head >= 1000)
{
return 1;
}
return 0;
}