相关链接
题目传送门：http://paste.ubuntu.com/23686161/
解题报告
这题好神啊！
首先这题是三维几何，大家都不是很会的样子
于是我们考虑用一个平行于y-z平面的平面A，沿着x轴扫描
于是三维的直线就变成了一个在二维平面上运动的点
现在考虑那个两两相交的边集
选定一个点为原点进行坐标变换后，其他点只会有两种情况：
- 同时经过原点
- 都在同一条经过原点的直线上以不同速度运动
于是暴力枚举那个点，然后sort之后搞一搞
在 \(O(nlogn)\) 的时间复杂度内就可以解决啦！
Code
#include<bits/stdc++.h>
#define LL long long
#define Vector Point
using namespace std;
const int N = 2000+9;
const double EPS = 1e-8;
const double STP = 1e3;
const double PI = acos(-1);
int n,vout;
double te[N];
struct Point{
double x,y;
inline Point() {}
inline Point(double _x, double _y):x(_x),y(_y) {}
inline Point operator + (const Point &B) {return Point(x+B.x, y+B.y);}
inline Point operator - (const Point &B) {return Point(x-B.x, y-B.y);}
inline Point operator * (const double a) {return Point(x*a, y*a);}
inline Point operator / (const double a) {return Point(x/a, y/a);}
inline double operator * (const Point &B) {return x*B.x + y*B.y;}
inline double operator ^ (const Point &B) {return x*B.y - y*B.x;}
inline double operator / (const Point &B) {if(abs(x)>EPS)return x/B.x; else return y/B.y;}
inline double len() {return sqrt(x*x + y*y);}
}ori[N],sta[N],spd[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int solve(double *arr, int tot) {
sort(arr+1, arr+1+tot);
int ret = 0;
for (int l=1,r;l<=tot;l=r+1) {
for (r=l;r<tot&&abs(arr[l]-arr[r+1])<EPS;r++);
ret = max(r - l + 1, ret);
}
return ret;
}
inline bool cmp(const Vector &A, const Vector &B) {
if (abs(A.x-B.x)<EPS) return A.y < B.y;
return A.x < B.x;
}
inline int solve(Vector *arr, int tot) {
sort(arr+1, arr+1+tot, cmp);
int ret = 0;
for (int l=1,r,mx=0;l<=tot;l=r+1,mx=0) {
for (r=l;r<tot&&abs(arr[l].x-arr[r+1].x)<EPS;r++);
for (int i=l+1;i<=r;i++) if (abs(arr[i].y-arr[i-1].y)<EPS) mx++;
ret = max(ret, r - l + 1 - mx);
}
return ret;
}
int main() {
freopen("gentech.in","r",stdin);
freopen("gentech.out","w",stdout);
n = read();
for (int i=1;i<=n;i++) {
double x1,x2; Point p1,p2;
x1 = read(); p1.x = read(); p1.y = read();
x2 = read(); p2.x = read(); p2.y = read();
ori[i] = (p1 - p2) / (x1 - x2) * STP;
sta[i] = (p1 - p2) / (x1 - x2) * (STP - x1) + p1;
}
for (int k=1,tot=0;k<=n;k++,tot=0) {
for (int i=1;i<=n;i++) {
if (i != k) {
Point bas = sta[i] - sta[k];
Vector cur = ori[i] - ori[k];
if (abs(bas ^ cur) < EPS) {
te[++tot] = bas / cur;
spd[tot].x = atan2(cur.y, cur.x);
spd[tot].y = cur.len();
}
}
}
vout = max(vout, solve(te, tot));
vout = max(vout, solve(spd, tot));
}
printf("%d\n",vout+1);
return 0;
}
There is definately a great deal to learn about this topic.
I love all of the points you made.
Hi it’s me, I am also visiting this web site regularly, this web site is in fact nice and the people are truly
sharing pleasant thoughts.
You really make it appear really easy together with your presentation however I in finding
this matter to be really one thing which I think I would never understand.
It seems too complicated and extremely broad for me.
I’m having a look forward to your next submit, I’ll try
to get the dangle of it!
I don’t even know how I ended up here, but I thought this post was great.
I don’t know who you are but definitely you are going to a famous blogger if
you are not already 😉 Cheers!
Fantastic post however , I was wondering if you could write a litte more
on this topic? I’d be very thankful if you could elaborate a little bit more.
Many thanks!
Greate post. Keep writing such kind of info on your page.
Im really impressed by it.
Hey there, You’ve performed an excellent job. I’ll certainly digg it and for
my part recommend to my friends. I am confident they’ll be benefited from this site.
Hi there! This is my first visit to your blog!
We are a collection of volunteers and starting a new project in a community in the same niche.
Your blog provided us useful information to work
on. You have done a outstanding job!
For latest news you have to pay a visit the web and on internet I found this website as a finest web
page for hottest updates.
Oh my goodness! Impressive article dude! Thanks, However
I am going through troubles with your RSS. I don’t know the reason why I am unable to subscribe to it.
Is there anybody else having the same RSS problems?
Anyone who knows the solution can you kindly respond?
Thanks!!
Whats up are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get
started and set up my own. Do you require any coding expertise to make
your own blog? Any help would be greatly appreciated!
Paragraph writing is also a excitement, if
you be acquainted with then you can write or else it is complex
to write.
you are really a excellent webmaster. The site loading velocity is amazing.
It sort of feels that you’re doing any distinctive trick.
Furthermore, The contents are masterpiece. you’ve done a wonderful
process on this matter!
Excellent article. I will be going through many of
these issues as well..
really awesome article. i share you this!! We love the children. because they are the best thing we see in the world.like me i really love childrens .I’m happy when I see kids happy too.kindly visit me here just click it.
im long time of my work I just saw very good ones and very quick to understand.kindly visit us.
amazing very nice comment here i really like this. please try to visit me here.
It is not my first time to pay a quick visit this site, i am
browsing this web page dailly and get pleasant facts from here all
the time.
Some genuinely nice stuff on this site, I like it.
Unquestionably believe that which you said. Your favorite reason appeared to be on the web the easiest thing to be
aware of. I say to you, I definitely get irked while people think about worries that they plainly do not know about.
You managed to hit the nail upon the top as well as defined out the whole thing without
having side effect , people can take a signal.
Will probably be back to get more. Thanks
Hi there, yeah this article is really nice and I have learned
lot of things from it concerning blogging.
thanks.
Hey would you mind letting me know which hosting company you’re working with?
I’ve loaded your blog in 3 different browsers and I must say this blog
loads a lot faster then most. Can you suggest a good web hosting provider at a fair price?
Kudos, I appreciate it!
Good information. Lucky me I discovered your site
by chance (stumbleupon). I have book-marked it
for later!
You really make it appear really easy together with
your presentation however I to find this matter to be actually
one thing which I believe I’d by no means understand.
It kind of feels too complex and very vast for me.
I’m taking a look ahead in your subsequent publish, I will
try to get the cling of it!
Hello, its nice piece of writing about media print, we all be familiar with media is a
fantastic source of facts.
Wow! This blog looks exactly like my old one! It’s on a completely different subject but
it has pretty much the same layout and design. Outstanding choice of colors!
Excellent beat ! I would like to apprentice while you amend your web site, how can i subscribe
for a blog web site? The account aided me a acceptable deal.
I had been tiny bit acquainted of this your broadcast
provided bright clear idea
I simply could not depart your web site prior
to suggesting that I extremely loved the standard info an individual supply in your visitors?
Is gonna be again continuously to investigate
cross-check new posts
First off I would like to say terrific blog! I had a quick question that I’d like to ask if you don’t mind.
I was interested to know how you center yourself and clear
your mind before writing. I have had a hard time clearing my mind in getting my ideas out.
I truly do take pleasure in writing but it just seems like the first 10 to 15 minutes are generally wasted just trying to figure out how
to begin. Any ideas or hints? Thank you!
I read this paragraph fully concerning the difference of newest and
previous technologies, it’s awesome article.
Hmm it looks like your website ate my first comment (it was
super long) so I guess I’ll just sum it up what I wrote and say, I’m thoroughly
enjoying your blog. I as well am an aspiring blog blogger but I’m
still new to the whole thing. Do you have any helpful
hints for newbie blog writers? I’d certainly appreciate it.
I’m impressed, I must say. Really hardly ever do I encounter a blog that’s both educative and entertaining, and let me let you know, you have hit the nail on the head. Your idea is outstanding; the issue is one thing that not enough individuals are speaking intelligently about. I am very glad that I stumbled across this in my search for one thing referring to this.