| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 895044 |
2023-12-29T11:15:26 Z |
Litusiano |
Wish (LMIO19_noras) |
C++17 |
|
1 ms |
348 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e4+5;
const int SUM = 1e9;
const double EPS = 1e-9;
double DIST;
double DIST1;
double dist(double x, double y, int x1, int y1){
return sqrt((x-x1) * (x-x1) + (y-y1)*(y-y1));
}
double findtime(double x0, double y0, int inx, int iny, double mod){
double d = dist(x0,y0, inx, iny);
double t = d/mod;
return t;
}
bool check(double x, double y, int inx, int iny){
if(DIST > EPS) return (x-inx)*DIST >= 0;
return (y-iny) * DIST1 >= 0;
}
int fl(double x){
int y = x+EPS;
// cerr<<"FLOOR "<<x<<" "<<y<<" "<<abs(y-x)<<endl;
if(abs(y-x) < 2*EPS) return y;
int z = floor(x+EPS);
return z;
}
int ce(double x){
int y = x+EPS;
if(abs(y-x) < 2*EPS) return y;
int z = ceil(x+EPS);
return z;
}
vector<pair<int,int>> intersect(double r, double a, double b, double c, double mod, int inx, int iny, bool isin){
vector<pair<int,int>> ans;
// given as input
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
return ans;
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
// CALC TIME IN THIS POINT AND RETURN
double t = findtime(x0,y0,inx,iny,mod);
int t1 = fl(t);
int t2 = ce(t);
if(!check(x0,y0, inx,iny)) return ans;
if(isin){
ans.push_back({0,t1});
}
else if(t1 == t2){
ans.push_back({t1,t2});
}
return ans;
// cout << x0 << ' ' << y0 << '\n';
}
else {
double d = r*r - c*c/(a*a+b*b);
double mult = sqrt (d / (a*a+b*b));
double ax, ay, bx, by;
ax = x0 + b * mult;
bx = x0 - b * mult;
ay = y0 - a * mult;
by = y0 + a * mult;
// cerr<<ax<<" "<<ay<<" "<<bx<<" "<<by<<" "<<check(ax,ay,inx,iny)<<" "<<check(bx,by,inx,iny)<<endl;
// CHECK POINTS
double t = findtime(ax,ay,inx,iny,mod);
double t1 = findtime(bx,by,inx,iny,mod);
if(t > t1) swap(t,t1);
if(check(ax,ay, inx, iny) && check(bx,by, inx,iny)){
int ti = ce(t); int tf = fl(t1);
// cerr<<"TIMES "<<t<<" "<<ti<<" "<<t1<<" "<<tf<<endl;
if(tf < ti) return ans;
ans.push_back({ti,tf});
}
else if(check(ax,ay, inx,iny)){
int ti = fl(t);
if(isin) ans.push_back({0,ti});
}
else if(check(bx,by, inx,iny)){
int ti = fl(t1);
if(isin) ans.push_back({0,ti});
}
// puts ("2 points");
// cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
return ans;
}
}
bool cmp(pair<int,int> a, pair<int,int> b){
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
bool isin(int a, int b, int r){
return (a*a + b*b) <= r;
}
signed main(){
// cout<<setprecision(10)<<fixed;
int n; cin>>n;
int r; cin>>r;
vector<pair<int,int>> segs;
for(int i = 0; i<n; i++){
int a,b,c,d; cin>>a>>b>>c>>d;
if(c == a){
swap(a,b); swap(c,d);
}
DIST = c-a;
DIST1 = d-b;
// if(abs(b) > r) continue;
// a+=SUM; b+=SUM; c+=SUM; d+=SUM;
double B = (1.0*d-b) / (1.0 * c - a);
double C = b-B*a;
vector<pair<int,int>> s = intersect(r,-B,1,-C, sqrt((1.0*d-b)*((1.0*d-b)) + (1.0 * c - a) * (1.0 * c - a)), a,b, isin(a,b,r));
for(auto x : s){
// cerr<<"HERE "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<x.first<<" "<<x.second<<endl;
segs.push_back({x.first,0});
segs.push_back({x.second,1});
}
}
sort(segs.begin(),segs.end());
int op = 0; int cl = 0;
int ans = 0;
for(auto x : segs){
if(x.second == 0) op++;
else cl++;
ans = max(ans, op-cl);
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
