Pagini recente » Cod sursa (job #844206) | Cod sursa (job #2339616) | Cod sursa (job #140018) | Cod sursa (job #1645186) | Cod sursa (job #1863598)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("oypara.in");
ofstream g("oypara.out");
int N;
const int NMax = 100005;
pair <int, int> P[2][NMax], S[2][NMax];
int top[2];
int ind;
char Str[60];
void Read()
{
f >> N;
f.get();
for(int i = 1; i <= N; i++)
{
f.getline(Str, 60);
int cnt = 0, val = 0;
int x, y1, y2 = -1;
for(int j = 0; Str[j] != 0; j++)
{
if(Str[j] >= '0' && Str[j] <= '9')
val = val * 10 + Str[j] - '0';
if(Str[j] == ' ')
{
++cnt;
if(cnt == 1)
x = val;
if(cnt == 2)
y1 = val;
if(cnt == 3)
y2 = val;
val = 0;
}
}
if(y2 == -1)
y2 = val;
P[0][i] = make_pair(x, y2);
P[1][i] = make_pair(x, y1);
}
}
inline long long Area(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
return 1LL * a.first * b.second + 1LL * b.first * c.second + 1LL * c.first * a.second - 1LL * a.second * b.first - 1LL * b.second * c.first - 1LL * c.second * a.first;
}
inline bool cmp(pair <int, int> a, pair <int, int> b)
{
long long area = Area(P[ind][1], a, b);
if(area == 0)
return a < b;
return area > 0;
}
void Graham()
{
pair <int, int> Min = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
int PMin = 1;
for(int i = 1; i <= N; i++)
{
if(P[ind][i] < Min)
{
Min = P[ind][i];
PMin = i;
}
}
swap(P[ind][PMin], P[ind][1]);
sort(P[ind] + 2, P[ind] + N + 1, cmp);
top[ind] = 0;
S[ind][++top[ind]] = P[ind][1];
for(int i = 2; i <= N; i++)
{
while(top[ind] > 1 && Area(P[ind][i], S[ind][top[ind]], S[ind][top[ind] - 1]) >= 0)
--top[ind];
S[ind][++top[ind]] = P[ind][i];
}
}
inline bool check(int i, int j)
{
long long sign = Area(S[1][i], S[0][j], S[0][j - 1]), sign2 = Area(S[1][i], S[0][j], S[0][j + 1]);
if(sign < 0)
sign = -1;
if(sign > 0)
sign = 1;
if(sign2 < 0)
sign2 = -1;
if(sign2 > 0)
sign2 = 1;
return sign == sign2 || sign == 0 || sign2 == 0;
}
inline bool check2(int i, int j)
{
long long sign = Area(S[0][j], S[1][i], S[1][i - 1]), sign2 = Area(S[0][j], S[1][i], S[1][i + 1]);
if(sign < 0)
sign = -1;
if(sign > 0)
sign = 1;
if(sign2 < 0)
sign2 = -1;
if(sign2 > 0)
sign2 = 1;
return sign == sign2 || sign == 0 || sign2 == 0;
}
void Solve()
{
S[0][0] = S[0][top[0]];
S[1][0] = S[1][top[1]];
S[0][++top[0]] = S[0][1];
S[1][++top[1]] = S[1][1];
int j = 1;
for(int i = top[1]; i >= 1; i--)
{
while(j <= top[0] && check(i, j) == 0)
++j;
if(j <= top[0] && check2(i, j) == 1 && S[0][j].first != S[1][i].first)
{
g << S[1][i].first << " " << S[1][i].second << " " << S[0][j].first << " " << S[0][j].second << "\n";
break;
}
}
}
int main()
{
Read();
ind = 0;
Graham();
ind++;
Graham();
Solve();
return 0;
}