MILITARY - Câu chuyện người lính
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec { int x,y,d; };
int n,re,d[4444];
vector <rec> a,b;
bool cmp(rec i,rec j)
{
return i.d<j.d || (i.d==j.d && (i.y<j.y || (i.y==j.y && i.x<j.x)));
}
double cotan(int x,int y)
{
int xx=a[0].x, yy=a[0].y;
if (y==yy) return 27081993;
return 1.0*(x-xx)/(y-yy);
}
int dist(int x,int y)
{
int xx=a[0].x, yy=a[0].y;
return (x-xx)*(x-xx)+(y-yy)*(y-yy);
}
bool cmpp(rec i,rec j)
{
double ii=cotan(i.x,i.y), jj=cotan(j.x,j.y);
int id=dist(i.x,i.y), jd=dist(j.x,j.y);
return ii>jj || (ii==jj && id>jd);
}
int area(rec i,rec j,rec k)
{
int s=(j.x-i.x)*(j.y+i.y)+(k.x-j.x)*(k.y+j.y)+(i.x-k.x)*(i.y+k.y);
return s;
}
int main()
{
int i,j;
rec u;
cin >> n;
fr(i,1,n)
{
u.d=0;
scanf("%d%d",&u.x,&u.y);
a.push_back(u);
}
while (1)
{
sort(a.begin(),a.end(),cmp);
fr(n,0,int(a.size())-1)
if (a[n].d) break;
if (n<3) break;
a.resize(n);
sort(a.begin()+1,a.end(),cmpp);
b.clear();
b.push_back(a[0]);
a[0].d=1; b[0].d=0;
fr(j,1,n-1)
if (a[j].x!=a[0].x || a[j].y!=a[0].y) break;
if (j==n) break;
b.push_back(a[j]);
a[j].d=1; b[1].d=j;
fr(i,j+1,n-1)
{
while (b.size()>1 && area(a[i],b[b.size()-1],b[b.size()-2])<=0)
{
a[b[b.size()-1].d].d=0;
b.pop_back();
}
b.push_back(a[i]);
a[i].d=1; b[b.size()-1].d=i;
}
if (b.size()>2) re++;
int m=b.size();
fr(i,1,n-1)
{
if (cotan(a[i].x,a[i].y)==cotan(b[1].x,b[1].y)) a[i].d=1;
if (cotan(a[i].x,a[i].y)==cotan(b[m-1].x,b[m-1].y)) a[i].d=1;
}
fr(i,1,m-2)
{
int l=b[i].d, r=b[i+1].d;
fr(j,l+1,r-1)
if (!area(b[i+1],a[j],b[i])) a[j].d=1;
}
}
cout << re << endl;
return 0;
}