#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll ccw(pll a, pll b, pll c) {
return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
pll arr[300100];
struct str {
int s, e;
str(){}
str(int s, int e):s(s),e(e){}
bool operator < (const str &A) const {
return (arr[e].y-arr[s].y)*(arr[A.e].x-arr[A.s].x)<
(arr[A.e].y-arr[A.s].y)*(arr[e].x-arr[s].x)||
(((arr[e].y-arr[s].y)*(arr[A.e].x-arr[A.s].x)==
(arr[A.e].y-arr[A.s].y)*(arr[e].x-arr[s].x))&&s>A.s);
}
bool operator == (const str &A) const {
return s==A.s&&e==A.e;
}
};
int n;
ll c;
priority_queue<str> pq;
int chk[300100];
int par[300100];
int fin(int a) {
if (a<=0) return a;
return par[a] = (chk[a]?a:fin(par[a]));
}
ll gcd(ll a, ll b) {
if (!a) return b;
return gcd(b%a,a);
}
void print(str piv) {
ll a = arr[piv.e].y-arr[piv.s].y, b = arr[piv.e].x-arr[piv.s].x;
printf("%lld/%lld\n",a/gcd(a,b),b/gcd(a,b));
exit(0);
}
int main() {
int i;
scanf("%d%lld",&n,&c); c*=2;
for (i=0;i<n;i++) scanf("%lld",&arr[i].x);
for (i=0;i<n;i++) scanf("%lld",&arr[i].y);
for (i=0;i+1<n;i++) pq.push(str(i,i+1));
for (i=0;i<n;i++) chk[i] = 1;
for (i=0;i<n;i++) par[i] = i-1;
while(!pq.empty()) {
str piv = pq.top();
pq.pop();
if (!chk[piv.s]||!chk[piv.e]) {
continue;
}
if (piv.s==0) print(piv);
int v = fin(piv.s-1);
if (c<ccw(arr[v],arr[piv.s],arr[piv.e])) print(piv);
//printf("%d, %d, %d : %lld\n",v,piv.s,piv.e,ccw(arr[v],arr[piv.s],arr[piv.e]));
c-=ccw(arr[v],arr[piv.s],arr[piv.e]);
chk[piv.s] = 0;
pq.push(str(v,piv.e));
}
printf("-1\n");
return 0;
}
Compilation message
hill.cpp: In function 'int main()':
hill.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld",&n,&c); c*=2;
~~~~~^~~~~~~~~~~~~~~~
hill.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<n;i++) scanf("%lld",&arr[i].x);
~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:56:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<n;i++) scanf("%lld",&arr[i].y);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Runtime error |
693 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Runtime error |
693 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
