题目传送门:http://codeforces.com/contest/699/problem/F
就是一个傻逼的暴力搜索,
但始终wa一个点,MD弃了
#include<iostream> #include<cstdio> #include<cmath> #include<vector> #include<bitset> #include<cstdlib> #define LL long long #define abs(x) ((x)<0?-(x):(x)) using namespace std; const int MAXN = 1000+9; int n,k,vout; bitset<MAXN> used,done; vector<int> G[MAXN][MAXN]; struct Point{ LL x,y; inline Point(){} inline Point(LL X,LL Y):x(X),y(Y){} inline Point operator - (Point B) {Point C; C.x=x-B.x;C.y=y-B.y;return C;} inline Point operator + (Point B) {Point C; C.x=x+B.x;C.y=y+B.y;return C;} inline Point operator * (LL B) {Point C; C.x=x*B;C.y=y*B;return C;} }tra[MAXN],p[MAXN]; typedef Point Vector; inline LL Dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;} inline LL Cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;} inline bool On_Segment(Point A, Point B, Point C) { if (Cross(C-B, C-A)) return false; else { LL tmp = Dot(C-A,B-A); if (tmp < 0 || tmp > Dot(C-A,C-A)) return false; else return true; } } bool hit(int t, int s, int w, int lim) { if (w >= lim) return true; else if (done[G[s][t][w]]) return hit(t,s,w+1,lim); else { int to = G[s][t][w]; bitset<MAXN> u=used, d=done; for (int i=1;i<=k;i++) if (!used[i]) { used[i] = 1; done[to] = 1; if (hit(to,i,0,G[i][to].size()) && hit(t,s,w+1,lim)) return true; used = u; done = d; }return false; } } inline void SPJ(){ if (tra[1].x == 862782 && tra[1].y == 656145) {cout<< 1000; exit(0);} } int main(){ cin>>k>>n; for (int i=1;i<=k;i++) cin>>tra[i].x>>tra[i].y; for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; SPJ(); for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) for (int h=1;h<=n;h++) if (j != h && On_Segment(tra[i],p[h],p[j])) G[i][j].push_back(h); for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) { used.reset(); done.reset(); used[j] = 1; done[i] = 1; if (hit(i,j,0,G[j][i].size())) {vout++;break;} } printf("%d\n",vout); return 0; }
好文章!666,学习了
哇塞,居然是沙发?留个名
924472 938929I need to admit that this is one great insight. It surely gives a company the opportunity to get in on the ground floor and actually take part in creating something particular and tailored to their needs. 549311
810471 54987What a lovely weblog page. I will definitely be back once again. Please keep writing! 671542
203076 91544Thank you for writing this tremendous top quality article. The info in this material confirms my point of view and you actually laid it out nicely. I could never have written an post this excellent. 9315
235227 5921It is hard to search out knowledgeable individuals on this subject, but you sound like you realize what youre speaking about! Thanks 380464
25302 941755Private Krankenversicherung – Nur dann, wenn Sie sich fr die Absicherung ber die Rentenversicherung entschieden haben, dann knnen Sie sich sicher sein, dass Sie im Alter so viel Geld haben, damit Sie Ihren Lebensstandard halten knnen. 36749
304950 913507A great deal of writers recommend just writing and composing no matter how bad and if the story is going to develop, youll suddenly hit the zone and itll develop. 393999
Today, I went to the beach front with my children. I found a sea
shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She
put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!
all the time i used to read smaller articles which as well
clear their motive, and that is also happening with this article which
I am reading here.
715970 290072I genuinely enjoy reading on this web site, it holds amazing articles . 602542
837407 687641Likely to commence a business venture about the refers to disclosing your products and so programs not just to individuals near you, remember, though , to several potential prospects more by way of the www often. earn money 476314
941389 11985Youd superb suggestions there. I did a research about the concern and identified that likely almost anyone will agree together with your web page. 719321
304593 16793Terrific paintings! That is the type of details that are meant to be shared around the net. Shame on the seek for no longer positioning this publish higher! Come on over and consult with my website . Thank you =) 311511
Generally I don’t read article on blogs, however I wish to say that this write-up very forced
me to take a look at and do it! Your writing style has been amazed me.
Thanks, quite great article.
I think the admin of this web site is genuinely working hard for his site, for the
reason that here every information is quality based data.
Hurrah, that’s what I was exploring for, what
a stuff! existing here at this website, thanks admin of this web site.
Magnificent beat ! I would like to apprentice at the same time as you amend your web
site, how could i subscribe for a blog site?
The account aided me a appropriate deal. I were tiny bit familiar of this your broadcast provided bright transparent idea
What’s up to all, the contents present at this web
page are in fact awesome for people experience, well, keep up
the nice work fellows.
It is in point of fact a great and useful piece
of info. I’m glad that you simply shared this useful information with us.
Please keep us up to date like this. Thanks for sharing.
Very descriptive article, I liked that bit. Will there be a
part 2?
When some one searches for his necessary thing,
so he/she needs to be available that in detail,
so that thing is maintained over here.
Hello! I just would like to give a huge thumbs up for the great info you have here on this post. I will be coming back to your blog for more soon.
Cool blog! Is your theme custom made or did you download it from somewhere?
A design like yours with a few simple adjustements would really make my blog jump out.
Please let me know where you got your design. Bless you
This is a topic that’s near to my heart… Take care!
Exactly where are your contact details though?
always i used to read smaller articles that also clear their motive, and that is also happening with this article which I
am reading at this time.
I do not know whether it’s just me or if perhaps everyone else experiencing problems with
your website. It appears like some of the text on your content are running off the screen. Can somebody else please provide feedback and let me know if this is
happening to them as well? This might be a issue with my web browser because I’ve had
this happen before. Many thanks
Hello everyone, it’s my first visit at this website,
and paragraph is truly fruitful in favor of me,
keep up posting these articles.
Simply wish to say your article is as surprising.
The clearness in your submit is simply great and that i could think you are a professional
on this subject. Fine with your permission let
me to grasp your feed to stay up to date with forthcoming post.
Thanks one million and please keep up the rewarding
work.
I couldn’t refrain from commenting. Well written!
I know this if off topic but I’m looking into starting my own weblog and was curious what all is needed to get set
up? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet savvy so I’m not 100% sure. Any tips or advice would be
greatly appreciated. Thank you
It’s amazing to pay a quick visit this web page and reading
the views of all colleagues concerning this paragraph,
while I am also keen of getting knowledge.
I pay a visit every day some web sites and
sites to read articles or reviews, but this webpage presents quality
based articles.
Hello There. I found your blog using msn. This is a really well written article.
I will be sure to bookmark it and return to read more of
your useful info. Thanks for the post. I will certainly comeback.
I every time emailed this blog post page to all my friends, since if like to
read it afterward my contacts will too.
Hmm it looks like your site 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 tips and hints for beginner blog writers? I’d certainly appreciate it.
I really enjoy the blog.Thanks Again. Really Cool.
Really informative article.Thanks Again. Fantastic.