Submission #907220

#	Time	Username	Problem	Language	Result	Execution time	Memory
907220		NemanjaSo2005	Fence (CEOI08_fence)	C++17	0 / 100	1 ms	500 KiB

fence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M;
struct tacka{
   ll x,y;
   bool operator == (const tacka &a){
      return x==a.x and y==a.y;
   }
   tacka operator - (const tacka &a){
      tacka ret;
      ret.x=x-a.x;
      ret.y=y-a.y;
      return ret;
   }
   tacka operator + (const tacka &a){
      tacka ret;
      ret.x=x+a.x;
      ret.y=y+a.y;
      return ret;
   }
} R[105],G[105];
ll znak(ll x){
   if(x==0)
      return 0;
   if(x>0)
      return 1;
   return -1;
}
ll orijent(tacka p1,tacka p2,tacka a){
   if(p1.x==p2.x)
      return znak(p2.y-p1.y)*znak(p1.x-a.x)*-1;
   return znak((p2.y-a.y)*(p2.x-p1.x)-(p2.x-a.x)*(p2.y-p1.y));
}
bool inpolyg(vector<tacka> V,tacka p){
   V.push_back(V[0]);
   int ort=orijent(V[0],V[1],p);
   for(int i=2;i<V.size();i++)
      if(ort!=orijent(V[i-1],V[i],p))
         return false;
   return true;
}
bool svelevo(tacka p1,tacka p2){
   for(int i=1;i<=M;i++)
      if(orijent(p1,p2,G[i])==-1)
         return false;
   return true;
}
bool pox(tacka a,tacka b){
   if(a.x<b.x)
      return true;
   if(a.x>b.x)
      return false;
   return a.y<b.y;
}
vector<tacka> make_hull(vector<tacka> V){
   sort(V.begin(),V.end(),pox);
   vector<tacka> R;
   R.push_back(V[0]);
   for(int i=1;i<V.size();i++){
      if(V[i].x==V[0].x)
         continue;
      while(R.size()>=2){
         tacka p2=R.back();
         R.pop_back();
         tacka p1=R.back();
         R.push_back(p2);
         if(orijent(p1,p2,V[i])<0)
            break;
         R.pop_back();
      }
      R.push_back(V[i]);
   }

   tacka spec=R.back();
   for(int i=0;i<V.size();i++){
      if(V[i].x==R.back().x and V[i].y>spec.y)
         spec=V[i];
   }
   if(!(spec==R.back()))
      R.push_back(spec);

   for(int i=V.size()-1;i>=0;i--){
      if(V[i].x==R.back().x)
         continue;
      while(R.size()>=2){
         tacka p2=R.back();
         R.pop_back();
         tacka p1=R.back();
         R.push_back(p2);
         if(orijent(p1,p2,V[i])<0)
            break;
         R.pop_back();
      }
      R.push_back(V[i]);
   }
   if(R[0]==R.back())
      R.pop_back();
   return R;
}
vector<int> graf[105];
int prosli[105],pvred,res=1000;
void dfs(int gde,int d,int goal){
   if(gde==goal and d!=0)
      res=min(res,d+1);
   if(prosli[gde]==pvred)
      return;
   prosli[gde]=pvred;
   for(int p:graf[gde])
      dfs(p,d+1,goal);
}
int main(){
   cin>>N>>M;
   int oM=M;
   for(int i=1;i<=N;i++)
      cin>>R[i].x>>R[i].y;
   for(int i=1;i<=M;i++)
      cin>>G[i].x>>G[i].y;
   vector<tacka> V;
   for(int i=1;i<=N;i++)
      V.push_back(R[i]);
   V=make_hull(V);

/*   cout<<V.size()<<endl;
   for(int i=0;i<V.size();i++)
      cout<<V[i].x<<" "<<V[i].y<<endl;
   cout<<endl;*/

   for(int i=1;i<=M;i++)
      if(!inpolyg(V,G[i])){
         swap(G[M],G[i]);
         M--;
         i--;
      }

   for(int i=1;i<=N;i++)
      for(int j=1;j<=N;j++){
         if(i==j)
            continue;
         if(svelevo(R[i],R[j]))
            graf[i].push_back(j);
      }
   /*for(int i=1;i<=N;i++){
      cout<<i<<": ";
      for(int p:graf[i])
         cout<<p<<" ";
      cout<<endl;
   }*/

   for(int i=1;i<=N;i++){
      pvred++;
      dfs(i,0,i);
   }

  // cout<<M<<" "<<res<<endl;

   cout<<(oM-M)*111+res*20<<endl;
   return 0;
}
/*
5 1
0 0
100 0
0 100
100 100
53 46

20 20
*/

Compilation message (stderr)

fence.cpp: In function 'bool inpolyg(std::vector<tacka>, tacka)':
fence.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tacka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int i=2;i<V.size();i++)
      |                ~^~~~~~~~~
fence.cpp: In function 'std::vector<tacka> make_hull(std::vector<tacka>)':
fence.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tacka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for(int i=1;i<V.size();i++){
      |                ~^~~~~~~~~
fence.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tacka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10