#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]);
R.push_back(V[1]);
for(int i=2;i<V.size();i++){
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 dub[105],res=1000;
void dfs(int gde,int d){
if(dub[gde]!=0)
return;
dub[gde]=d;
for(int p:graf[gde]){
if(dub[p]!=0)
res=min(res,abs(dub[gde]-dub[p])+1);
else
dfs(p,d+1);
}
}
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);
}
dfs(1,1);
cout<<(oM-M)*111+res*20<<endl;
return 0;
}
Compilation message
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:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tacka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=2;i<V.size();i++){
| ~^~~~~~~~~
fence.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tacka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0;i<V.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
