| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1029558 |
2024-07-21T04:08:22 Z |
vjudge1 |
Wish (LMIO19_noras) |
C++17 |
|
1 ms |
4592 KB |
// 23 - 12 - 23
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define int long long
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
int n,r;
int a[MAX],b[MAX],c[MAX],d[MAX];
signed main(){
read();
cin >> n >> r;
// (x) ^ 2 + y ^ 2 = r ^ 2
// a[i] + t * u , b[i] + t * v
// (a + tu) ^ 2 + (b + tv) ^ 2 = r
// t ^ 2 * (u ^ 2 + v ^ 2) + 2t(au + bv) + a ^ 2 + b ^ 2 - r ^ 2 = 0
vector<ii> sweep;
for(int i = 1;i <= n;i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
int u = c[i] - a[i];
int v = d[i] - b[i];
int _a = u * u + v * v;
int _b = 2 * (a[i] * u + b[i] * v);
int _c = a[i] * a[i] + b[i] * b[i] - r * r;
// _aX^2 + _bX + _c = 0
int dental = _b * _b - 4 * _a * _c;
if(dental >= 0){
long double x_1 = (-_b - sqrt(dental)) / (2 * _a);
long double x_2 = (-_b + sqrt(dental)) / (2 * _a);
int inside = ceil(min(x_1,x_2));
int outside = floor(max(x_2,x_1));
if(inside <= outside){
//cout << i << " " << inside << " " << outside << "\n";
sweep.push_back({inside,0});
sweep.push_back({outside,1});
}
}
}
sort(sweep.begin(),sweep.end(),[&](const ii &a,const ii &b){
return (a.X == b.X) ? (a.Y < b.Y) : (a.X < b.X);
});
int res = 0;
int cnt = 0;
for(auto e : sweep){
cnt += (e.Y == 0 ? 1 : -1);
if(e.X >= 0)
res = max(res,cnt);
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4592 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4592 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4592 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4592 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4592 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
