Submission #895032

#	Time	Username	Problem	Language	Result	Execution time	Memory
895032		Litusiano	Wish (LMIO19_noras)	C++17	0 / 100	1 ms	348 KiB

noras

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e4+5;
const int SUM = 1e4;

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) < EPS) return y;
	int z = floor(x);
	return z;
}
int ce(double x){
	int y = x+EPS;
	if(abs(y-x) < EPS) return y;
	int z = ceil(x);
	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;
		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;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7