#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
struct Point
{
long long x,y;
};
Point operator-(Point a,Point b)
{
return {a.x-b.x,a.y-b.y};
}
long long operator*(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
}
int sgn(long long x)
{
return (x<0 ? -1:1);
}
int ilo(Point a,Point b,Point c)
{
return sgn((a-c)*(b-c));
}
bool cross(Point a,Point b,Point c,Point d)
{
return (ilo(c,b,a)!=ilo(d,b,a) && ilo(a,d,c)!=ilo(b,d,c));
}
bool inside(Point p,Point a,Point b,Point c)
{
int val=sgn((p-a)*(b-a));
if(sgn((p-b)*(c-b))==val && sgn((p-c)*(a-c))==val)
return true;
return false;
}
Point tab[N+10];
vector<int> hull;
bool onhull[N+10];
bool vis[N+10];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>tab[i].x>>tab[i].y;
sort(tab+1,tab+n+1,[](Point a,Point b){ return a.x<b.x; });
auto pop_bad=[](int x)
{
while(hull.size()>1 &&
(tab[x]-tab[hull[hull.size()-2]])*(tab[hull.back()]-tab[hull[hull.size()-2]])<0)
hull.pop_back();
hull.push_back(x);
return;
};
for(int i=1;i<=n;i++)
pop_bad(i);
for(int i=n-1;i>=1;i--)
pop_bad(i);
hull.pop_back();
for(auto v:hull)
onhull[v]=true;
//for(auto v:hull)
// cerr<<tab[v].x<<" "<<tab[v].y<<"\n";
for(int i=1;i<=n;i++)
{
if(onhull[i])
continue;
int a=1,b,c;
for(b=1,c=2;sgn((tab[hull[b]]-tab[a])*(tab[i]-tab[a]))==
sgn((tab[hull[c]]-tab[a])*(tab[i]-tab[a]));b++,c++);
b=hull[b];
c=hull[c];
for(int j=1;j<=n;j++)
{
if(j==i || j==a || j==b || j==c)
continue;
if(inside(tab[i],tab[a],tab[b],tab[j]))
c=j;
else if(inside(tab[i],tab[a],tab[j],tab[c]))
b=j;
else if(inside(tab[i],tab[j],tab[b],tab[c]))
a=j;
}
for(int j:{a,b,c})
{
if(vis[j])
continue;
bool ok=true;
for(int p=1;p<=n;p++)
{
if(p==i || p==j)
continue;
for(int q=p+1;q<=n;q++)
{
if(q!=i && q!=j && cross(tab[i],tab[j],tab[p],tab[q]))
{
ok=false;
break;
}
}
if(!ok)
break;
}
if(ok)
ans++;
}
vis[i]=true;
}
cout<<ans+hull.size()<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
