#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1);
struct Punct
{
long long x,y;
};
long long determinant (Punct a,Punct b,Punct c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
bool compare (Punct a, Punct b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
ll n,i,st[4005],q,viz[4005];
Punct v[1005];
struct Triangle
{
ll a,b,c;
};
ll ok[1005],primul;
vector <Triangle> triunghiuri;
long long ABS(long long x)
{
if (x>0)
{
return x;
}
return -x;
}
bool sgn(ll x)
{
if (x>=0)
{
return 1;
}
return 0;
}
bool seinter(pair <Punct,Punct> dreapta1,pair <Punct,Punct> dreapta2)
{
ll det1=determinant(dreapta1.first,dreapta1.second,dreapta2.first);
ll det2=determinant(dreapta1.first,dreapta1.second,dreapta2.second);
ll det3=determinant(dreapta2.first,dreapta2.second,dreapta1.first);
ll det4=determinant(dreapta2.first,dreapta2.second,dreapta1.second);
if (!det1||!det2||!det3||!det4)
{
return 0;
}
if (sgn(det1)==sgn(det2))
{
return 0;
}
if (sgn(det3)==sgn(det4))
{
return 0;
}
return 1;
}
ll Marc[1005][1005],j;
vector <pair <int,int>> candidati;
Punct P;
long double Angle (Punct O, Punct A) {
///AOX
Punct aux = {A.x - O.x, A.y - O.y};
long double ceau = atan2(aux.y, aux.x) * 180.0 / PI;
if (ceau<0)
{
ceau+=360;
}
return ceau;
}
bool compare2(int a,int b)
{
return Angle(P,v[a])<Angle(P,v[b]);
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n;
for (i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
}
sort (v+1,v+n+1,compare);
st[++q]=1;
st[++q]=2;
viz[1]=viz[2]=1;
for (i=3; i<=n; i++)
{
while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])<0)
{
viz[st[q]]=0;
q--;
}
viz[i]=1;
st[++q]=i;
}
for (i=n; i>=1; i--)
{
if (viz[i]==0)
{
while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])<0)
{
viz[st[q]]=0;
q--;
}
viz[i]=1;
st[++q]=i;
}
}
while (q>1&&determinant(v[st[q-1]],v[st[q]],v[1])<0)
{
q--;
}
for (i=1; i<=q; i++)
{
ok[st[i]]=1;
}
for (i=1; i<=n; i++)
{
if (ok[i]==0)
{
primul= i ;
break;
}
}
ok[primul]=1;
for (i=1; i<q; i++)
{
triunghiuri.push_back({st[i],st[i+1],primul});
}
triunghiuri.push_back({st[1],st[q],primul});
for (i=1; i<=n; i++)
{
if (ok[i]==0)
{
ll loc=0;
for (ll j=0; j<triunghiuri.size(); j++)
{
ll x=triunghiuri[j].a,y=triunghiuri[j].b,z=triunghiuri[j].c;
ll val1 = ABS(determinant(v[x],v[y],v[i]));
ll val2 = ABS(determinant(v[y],v[z],v[i]));
ll val3 = ABS(determinant(v[z],v[x],v[i]));
ll valfin = ABS(determinant(v[x],v[y],v[z]));
if (val1+val2+val3==valfin)
{
loc = j;
break;
}
}
Triangle triunghi1= {triunghiuri[loc].a,triunghiuri[loc].b,i};
Triangle triunghi2= {triunghiuri[loc].a,triunghiuri[loc].c,i};
Triangle triunghi3= {triunghiuri[loc].b,triunghiuri[loc].c,i};
triunghiuri.erase(triunghiuri.begin()+loc);
triunghiuri.push_back(triunghi1);
triunghiuri.push_back(triunghi2);
triunghiuri.push_back(triunghi3);
}
}
for (ll j=0; j<triunghiuri.size(); j++)
{
ll x=triunghiuri[j].a,y=triunghiuri[j].b,z=triunghiuri[j].c;
Marc[x][y]=Marc[y][x]=Marc[x][z]=Marc[z][x]=Marc[z][y]=Marc[y][z]=1;
}
for (i=1; i<=n; i++)
{
for (j=i+1; j<=n; j++)
{
if (Marc[i][j])
{
candidati.push_back({i,j});
}
}
}
ll sum=0;
for (i=0; i<candidati.size(); i++)
{
vector <int> neg,poz;
int ok1=1;
for (j=1;j<=n;j++)
{
if (j==candidati[i].first||j==candidati[i].second)
{
continue;
}
if (determinant(v[candidati[i].first],v[candidati[i].second],v[j])<0)
{
neg.push_back(j);
}
else
{
poz.push_back(j);
}
}
P = v[candidati[i].first];
Punct Q = v[candidati[i].second];
sort (neg.begin(),neg.end(),compare2);
sort (poz.begin(),poz.end(),compare2);
int st=-1;
for (j=0;j<neg.size();j++)
{
while (st+1<(int)poz.size()&&determinant(v[neg[j]],P,v[poz[st+1]])<0)
{
st++;
}
if (st==-1)
{
continue;
}
if (determinant(v[neg[j]],Q,v[poz[st]])>0)
{
ok1=0;
break;
}
}
sum=sum+ok1;
}
cout<<sum;
return 0;
}
Compilation message
geometrija.cpp: In function 'int main()':
geometrija.cpp:148:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Triangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (ll j=0; j<triunghiuri.size(); j++)
| ~^~~~~~~~~~~~~~~~~~~
geometrija.cpp:170:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Triangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for (ll j=0; j<triunghiuri.size(); j++)
| ~^~~~~~~~~~~~~~~~~~~
geometrija.cpp:186:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for (i=0; i<candidati.size(); i++)
| ~^~~~~~~~~~~~~~~~~
geometrija.cpp:210:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for (j=0;j<neg.size();j++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
