题解 Walker

总觉得有个柿子可以推……然而没推出来

考试的时候有个柿子假了导致我没想用两个点可以解出一组参数的事

假掉的柿子告诉我有不少东西能消掉

然而实际上随便选两个点高斯消元解出一组参数，再代入验证看够不够一半就行

因为至少有一半点是对的，1s内求不出解的概率极低

至于弧度值的正负：想想弧度的定义吧我半天没想明白它是啥

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100010

#define ll long long

//#define int long long 

int n;

const double eps=1e-6;

namespace task1{

	struct ele{

		double x, y, m, n, d1, d2;

		inline void build(double a1, double a2, double a3, double a4, double a5, double a6) {

			x=a1, y=a2, m=a3, n=a4, d1=a5, d2=a6;

		}

	}e[N<<1];

	inline bool operator < (ele a, ele b) {return fabs(a.d1-b.d1)<eps?a.d2<b.d2:a.d1<b.d1;}

	void solve() {

		scanf("%d", &n);

		double a, b, c, d;

		for (int i=1; i<=n; ++i) {

			scanf("%lf%lf%lf%lf", &a, &b, &c, &d);

			e[i].build(a, b, c, d, c-a, d-b);

		}

		sort(e+1, e+n+1);

		//for (int i=1; i<=n; ++i) cout<<e[i].d1<<' '<<e[i].d2<<endl;

		int pos1=1, pos2=1;

		for (int i=1; i<=n; ++i,++pos1,++pos2) {

			while (pos2+1<=n && fabs(e[pos2+1].d1-e[pos1].d1)<eps && fabs(e[pos2+1].d2-e[pos1].d2)<eps) ++pos2;

			if (pos2-pos1+1>=(n+1)/2) {

				printf("%.10lf\n", 0.0);

				printf("%.10lf\n", 1.0);

				printf("%.10lf %.10lf\n", e[pos1].d1, e[pos2].d2);

				exit(0);

			}

			pos1=pos2;

		}

	}

}

namespace task{

	double x[N], y[N], u[N], v[N], ans[N];

	struct matrix{

		double a[10][10];

		int n, m;

		void clear() {memset(a, 0, sizeof(a));}

		void resize(int a, int b) {n=a; m=b;}

		void put() {for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) cout<<a[i][j]<<' '; cout<<endl;}}

		void set(int i, double x1, double x2, double x3, double x4, double x5) {a[i][1]=x1; a[i][2]=x2; a[i][3]=x3; a[i][4]=x4; a[i][5]=x5;}

		void gauss(double ans[]) {

			for (int i=1; i<=n; ++i) {

				int r=i;

				for (int j=i+1; j<=n; ++j) if (fabs(a[j][i])>fabs(a[r][i])) r=j;

				if (r!=i) swap(a[i], a[r]);

				for (int j=1; j<=n; ++j) {

					if (i==j) continue;

					double d=a[j][i]/a[i][i];

					for (int k=i; k<=m; ++k) a[j][k]-=a[i][k]*d;

				}

			}

			for (int i=1; i<=n; ++i) ans[i]=a[i][m]/a[i][i];

		}

	}mat;

	void check(double x1, double y1, double m1, double n1, double x2, double y2, double m2, double n2) {

		mat.clear();

		mat.set(1, x1, -y1, 1.0, 0.0, m1);

		mat.set(2, y1, x1, 0.0, 1.0, n1);

		mat.set(3, x2, -y2, 1.0, 0.0, m2);

		mat.set(4, y2, x2, 0.0, 1.0, n2);

		mat.gauss(ans);

		double a, b, ak=ans[1], bk=ans[2], k, d1=ans[3], d2=ans[4];

		k = sqrt(ak*ak+bk*bk);

		a = ak/k; b = bk/k;

		int cnt=0;

		for (int i=1; i<=n; ++i) {

			if (fabs(ak*x[i]-bk*y[i]+d1-u[i])<eps && fabs(bk*x[i]+ak*y[i]+d2-v[i])<eps)

				if (++cnt>=(n+1)/2) {

					//cout<<"a: "<<a<<endl;

					//cout<<"b: "<<b<<endl;

					if (a>0&&b>0 || a<0&&b>0) printf("%.10lf\n", acos(a));

					else printf("%.10lf\n", -acos(a));

					printf("%.10lf\n", k);

					printf("%.10lf %.10lf\n", d1, d2);

					exit(0);

				}

		}

	}

	void solve() {

		srand(time(0));

		scanf("%d", &n);

		for (int i=1; i<=n; ++i) scanf("%lf%lf%lf%lf", &x[i], &y[i], &u[i], &v[i]);

		int a, b;

		mat.resize(4, 5);

		while (1) {

			do {a=rand()%n+1, b=rand()%n+1;} while (a==b);

			check(x[a], y[a], u[a], v[a], x[b], y[b], u[b], v[b]);

		}

	}

}

signed main()

{

	//task1::solve();

	task::solve();

	return 0;

}

巴特西

题解 Walker

最新文章

热门文章