#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <pair<int,int> > v1,v2,v3;
vector <int> ind,c1;
int x[105][105];
bool comp(int ind1,int ind2) {
return v2[ind1]<v2[ind2];
}
int ccw(pair <int,int> a,pair <int,int> b,pair <int,int> c) {
return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}
vector <int> convex_hull(vector <int> v) {
vector <int> g,d;
g.push_back(v[0]);
g.push_back(v[1]);
for(int i=2;i<v.size();i++) {
while(g.size()>=2 && ccw(v2[g[g.size()-2]],v2[g.back()],v2[v[i]])>0) {
g.pop_back();
}
g.push_back(v[i]);
}
reverse(v.begin(),v.end());
d.push_back(v[0]);
d.push_back(v[1]);
for(int i=2;i<v.size();i++) {
while(d.size()>=2 && ccw(v2[d[d.size()-2]],v2[d.back()],v2[v[i]])>0) {
d.pop_back();
}
d.push_back(v[i]);
}
g.pop_back();
d.pop_back();
for(int i=0;i<d.size();i++) {
g.push_back(d[i]);
}
return g;
}
int check(int ind1) {
for(int i=0;i<c1.size()-1;i++) {
if(ccw(v2[c1[i]],v2[c1[i+1]],v1[ind1])>0) return 0;
}
if(ccw(v2[c1.back()],v2[c1[0]],v1[ind1])>0) return 0;
return 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,sol=0;
cin >> n >> m;
for(int i=0;i<n;i++) {
int x,y;
cin >> x >> y;
v2.push_back(make_pair(x,y));
ind.push_back(i);
}
for(int i=0;i<m;i++) {
int x,y;
cin >> x >> y;
v1.push_back(make_pair(x,y));
}
sort(ind.begin(),ind.end(),comp);
c1=convex_hull(ind);
for(int i=0;i<m;i++) {
if(check(i)) v3.push_back(v1[i]);
}
sol+=111*(v1.size()-v3.size());
if(v3.size()==0) {
cout << sol;
return 0;
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
x[i][j]=1e9;
if(i==j) continue;
int a1=0;
for(int k=0;k<v3.size();k++) {
if(ccw(v2[i],v2[j],v3[k])>0) a1+=1;
}
if(!a1) {
x[i][j]=1;
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
for(int k=0;k<n;k++) {
x[j][k]=min(x[j][k],x[j][i]+x[i][k]);
}
}
}
int mini=1e9;
for(int i=0;i<n;i++) {
mini=min(mini,x[i][i]);
}
cout << sol+20*mini;
return 0;
}
Compilation message
fence.cpp: In function 'std::vector<int> convex_hull(std::vector<int>)':
fence.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=2;i<v.size();i++) {
| ~^~~~~~~~~
fence.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=2;i<v.size();i++) {
| ~^~~~~~~~~
fence.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0;i<d.size();i++) {
| ~^~~~~~~~~
fence.cpp: In function 'int check(int)':
fence.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i=0;i<c1.size()-1;i++) {
| ~^~~~~~~~~~~~
fence.cpp: In function 'int main()':
fence.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int k=0;k<v3.size();k++) {
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
