| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1095649 |
2024-10-02T19:11:24 Z |
MrPavlito |
Fence (CEOI08_fence) |
C++17 |
|
1 ms |
600 KB |
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 105;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,m;
vector<pii> polygon;
set<pii> deopolygona;
vector<vector<int>> graf(MAXN);
vector<bool> visited(MAXN);
vector<int> dist(MAXN);
int finalscore = 0;
int orientation(pii a, pii b, pii c)
{
double v = a.fi*(b.sc-c.sc) + b.fi*(c.sc-a.sc) + c.fi*(a.sc-b.sc);
if(v<0)return -1;
if(v>0)return 1;
return 0;
}
int kvadrat(int broj)
{
return broj*broj;
}
bool isclockwise(pii a, pii b, pii c)
{
int o = orientation(a,b,c);
return o<0;
}
bool isColinear(pii a, pii b, pii c)
{
return orientation(a,b,c) == 0;
}
void convexHull(vector<pii>& bandere)
{
pii p0 = {inf, inf};
for(int i=0; i<n; i++)
{
if(p0.sc > bandere[i].sc)p0 = bandere[i];
else if(p0.sc == bandere[i].sc && p0.fi > bandere[i].fi)p0 = bandere[i];
}
sort(bandere.begin(), bandere.end(), [&p0](const pii& a, const pii& b) {
int o = orientation(p0, a, b);
if (o == 0)
return kvadrat(p0.fi - a.fi) + kvadrat(p0.sc-a.sc)< kvadrat(p0.fi - b.fi) + kvadrat(p0.sc-b.sc);
return o < 0;
});
for(int i=0; i<n; i++)
{
while(polygon.size()>1 && !isclockwise(polygon[polygon.size()-2], polygon.back(), bandere[i]))polygon.pop_back();
polygon.pb(bandere[i]);
}
for(auto x: polygon)deopolygona.insert(x);
}
void bfs(int nod)
{
queue<pii> q;
for(auto x: graf[nod])q.push({x, 1});
while(!q.empty())
{
auto tr = q.front();
q.pop();
if(visited[tr.fi])continue;
visited[tr.fi] = 1;
dist[tr.fi] = tr.sc;
for(auto x: graf[tr.fi])
{
if(!visited[x])q.push({x, tr.sc+1});
}
}
}
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
cin >> n >> m;
vector<pii> bandere(n);
vector<pii> drveca(m);
vector<pii> availabledrvece;
vector<pii> availablebandere;
for(int i=0; i<n; i++)cin >> bandere[i].fi >> bandere[i].sc;
for(int i=0; i<m; i++)cin >> drveca[i].fi >> drveca[i].sc;
convexHull(bandere);
for(int i=0; i<m; i++)
{
bool jesteunutra = true;
for(int j=0; j<(int)polygon.size(); j++)
{
int o = orientation(polygon[j], polygon[(j+1)%(int)polygon.size()], drveca[i]);
if(o != -1)
{
jesteunutra = false;
break;
}
}
if(jesteunutra)availabledrvece.pb(drveca[i]);
}
if(availabledrvece.size() == 0)
{
cout << m*111 << endl;
return 0;
}
finalscore += (m - (int)availabledrvece.size())*111;
for(int i=0; i<n; i++)
{
if(deopolygona.count(bandere[i]))continue;
bool jesteunutra = true;
for(int j=0; j<(int)polygon.size(); j++)
{
int o = orientation(polygon[j], polygon[(j+1)%(int)polygon.size()], bandere[i]);
if(o != -1)
{
jesteunutra = false;
break;
}
}
if(jesteunutra)availablebandere.pb(bandere[i]);
}
for(auto x: polygon)availablebandere.pb(x);
int N = (int)availablebandere.size();
for(int i=0; i<N-1; i++)
{
for(int j = i+1; j<N; j++)
{
pii a= availablebandere[i];
pii b= availablebandere[j];
bool moze = true;
for(auto x: availabledrvece)
{
int o = orientation(a,b,x);
if(o != -1)
{
moze = 0;
break;
}
}
if(moze)graf[i].pb(j);
moze = true;
for(auto x: availabledrvece)
{
int o = orientation(b,a,x);
if(o != -1)
{
moze = 0;
break;
}
}
if(moze)graf[j].pb(i);
}
}
int rez = inf;
for(int i=0; i<N; i++)
{
fill(all(dist), inf);
fill(all(visited), 0);
bfs(i);
rez = min(rez, dist[i]);
}
cout << finalscore + rez*20 << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
