Submission #532632

#TimeUsernameProblemLanguageResultExecution timeMemory
532632stefantagaGeometrija (COCI21_geometrija)C++14
0 / 110
3 ms460 KiB
#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<poz.size();j++) { while (st+1<(int)neg.size()&&determinant(v[poz[j]],P,v[neg[st+1]])>0) { st++; } if (st==-1) { continue; } if (determinant(v[poz[j]],Q,v[neg[st]])<0) { ok1=0; break; } } sum=sum+ok1; } cout<<sum; return 0; }

Compilation message (stderr)

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<poz.size();j++)
      |                  ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...