Cow School [Jacob Steinhardt, 2006]

Bessy is going to school and doing well. She has taken N (1 <= N <= 5000 -- except one case where 1 <= N <= 50,000) tests and recorded the scores (T_i points out of P_i points for test i; 0 <= T_i <= P_i < 40,000; 0 < P_i) as this task's input. Her teacher will drop the D tests with the lowest percentage (T_i/P_i) before calculating Bessie's final grade (which is the sum of the remaining test score points over the sum of the remaining total test points). Bessy is good at math and quickly realizes that this does not benefit her as much as it might. To prove her point, Bessy wants to find all values of D for which she could have ended up with a higher grade by choosing to drop different tests than the teacher would have. Help her by finding and printing all values of D for which this is possible. Bessy has noted that, amazingly, she has never scored the same percentage on two different tests. PROBLEM NAME: schul INPUT FORMAT: * Line 1: A single integer, N * Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and P_i SAMPLE INPUT (file schul.in): 5 1 2 5 9 3 8 4 10 1 3 INPUT DETAILS: Bessy has taken 5 tests so far and has scores of 1/2, 5/9, 3/8, 4/10, and 1/3. OUTPUT FORMAT: * Line 1: A single integer K (0 <= K <= N) that is the number of values of D for which Bessy could have ended up with a higher grade by dropping a different set of D tests than the teacher. * Lines 2..K+1: The values of D for which this is true, in ascending numerical order. SAMPLE OUTPUT (file schul.out): 2 1 2 OUTPUT DETAILS: For D = 1, dropping 1/3 leads to a final grade of 13/29. A higher final grade of 11/24 can be achieved if Bessy drops 3/8. For D = 2, dropping 1/3 and 3/8 lead to a final grade of 10/21. A higher final grade of 7/14 can be achieved if Bessy drops 3/8 and 4/10.

ძროხების სკოლა – ლუკა მაჭარაძის თარგმანი

ახალი ბეღელი სიღარიბეში გატარებული წლების შემდეგ ფერმერმა ჯონმა გადაწყვიტა აეშენებინა ახალი ბეღელი. მას სურს, რომ ბეღელი მაქსიმალურად ხელმისაწვდომი იყოს და მან იცის საძოვრის კოორდინატები N(2 <= N <= 10,000) ძროხისთვის. ყველა საძოვრის კოორდინატი მთელი რიცხვია (X_i, Y_i) (-10,000 <= X_i , Y_i<= 10,000). მშიერი ძროხები არასოდეს ძოვენ ისეთ საძოვრებზე, რომლებიც ერთმანეთის მეზობლად მდებარეობენ(ჰორიზონტალურად, ან ვერტიკალურად). ბეღელი უნდა მდებარეობდეს მთელ კოორდინატებზე და არ უნდა ემთხვეოდეს რომელიმე საძოვარს. თითოეული ძროხის დაბრკოლების კოეფიციენტი მოცემულია ფორმულით |X-X_i|+|Y-Y_i|,სადაც (X,Y)ბეღელის კოორდინატებია და (X_i, Y_i) კი ამ ძროხის საძოვრის. სად უნდა ავაშენოთ ბეღელი, რომ ძროხების დაბრკოლების კოეფიციენტების ჯამი იყოს მინიმალური? ამოცანის სახელი: newbarn შესატანი ფაილის ფორმატი: *ხაზი 1: მთელი რიცხვი: N *ხაზები 2..N+1: ხაზი i+1 შეიცავს ორ ჰარით გამოყოფილ მთელ რიცხვს, საძოვრების კოორდინატებს (X_i, Y_i)i_ური ძროხისთვის. შესატანი ფაილის მაგალითი: 4 1 -3 0 1 -2 1 1 -1 შესატანი ფაილის მაგალითის დეტალები: მდელო მოიცავს 4 ძროხას თავისი საძოვრებით (1, -3), (0, 1), (-2, 1), (1, -1) წერტილებზე. გამოსატანი ფაილის ფორმატი: *ხაზი 1: ორი ჰარით გამოყოფილი მთელი რიცხვი: მინიმალური დაბრკოლება და წერტილების რაოდენობა , რომლებზეც შეუძლია ფერმერ ჯონს ააშენოს ბეღელი რომ მიიღოს მინიმალური დაბრკოლება. გამოსატანი ფაილის მაგალითი: 10 4 გამოსატანი ფაილის მაგალითის დეტალები: მინიმალური დაბრკოლება არის 10 და არსებობს 4 წერტილი რომლებზედაც ბეღელის აშენების შემდეგ მივიღებთ მინიმუმს: (0, -1), (0, 0), (1, 0) და (1, 1).

cow school

Suppose that for a particular value of D, using the teacher's choices gives a ratio of M, and Bessie wants to improve this ratio. If she things of every test as being M plus or minus some number of marks (not percent), then she will want to drop the tests with the minimum number of marks over M, and keep those with the most marks over M. If it happens that the teacher's choice is different, then she can switch some of the tests to get more than 0 over M and thus improve her score. A first attempt would be to verify this independently for each D. That is, for each D, determine the teacher-assigned mark, and look for the worst test kept in by the teacher and the best test dropped by the teacher ("better" meaning more marks above M). If substituting one for the other improves Bessie's score, then save this value of D. This gives an O(N^2) solution. Quite a few contestants tried to insert heuristics into their code to improve runtime. Most of these relied on some assumption about the 'density' of the solution points and the locations where the min/max occurs. It was rather difficult to construct a data which fails both heuristics based on upper and lower bound, so two contestants still manged to get by with heuristic solutions. There are several ways to go from here to get down to a O(nlogn) solution. First notice that the problem essentially reduces to finding the maximum/minimum values of the linear combination of a set of two variables. It suffices to consider the minimum case since the maximum case is a mirror equivalent. This can be thought as of either the x-intercepts of points on a plane or as the position where a certain line intersect a vertical line with a fixed x value. In both methods of visualization, it can be noticed that if a point is concave in relation to its two immediate neighbors, it can be deleted. Both methods immediately leads to a O(nlogn) time solution using balanced binary trees. This can be explained in professor Brian Dean's animated notes found at: http://www.cs.clemson.edu/~bcdean/cowschool.swf This is also the only type of O(nlogn) solution implemented during the contest. Sorry to all the Pascal programmers as STL set gives C++ users a huge advantage should this solution be implemented. Nima Ahmadi Pour from Iran was the only person to implement one correctly (although Adrian Kuegel did come close). Nima's code is here: #include <cstdlib> #include <cstdio> #include <algorithm> #include <set> #include <utility> using namespace std; double eps=1e-8; FILE *fin=fopen("schul.in","r"); FILE *fout=fopen("schul.out","w"); struct test{ int a,b; test(){} test(int t1,int t2):a(t1),b(t2){} }; bool operator<(const test& t1,const test& t2){ return t1.a*t2.b<t2.a*t1.b; } struct line{ int a,b; line(){} line(int t1,int t2):a(t1),b(t2){} }; bool operator<(const line& l1,const line& l2){ return l1.b<l2.b; } set<line> s; line last_line; double last_x; void reset(){ s.clear(); } double xinter(const line& l1,const line& l2){ return double(l1.a-l2.a)/double(l2.b-l1.b); } double yinter(const line& l1,double x){ return l1.b*x+l1.a; } double best(double x){ double ans=-1e12; set<line>::iterator it=s.find(last_line); while (it!=s.end() && yinter(*it,x)>ans){ ans=yinter(*it,x); ++it; } --it; last_x=x; last_line=*it; return ans; } void insert(const line& l){ while (true){ set<line>::iterator it1=s.lower_bound(l); if (it1==s.end()) break; set<line>::iterator it2=it1;++it2; if (it2==s.end()) break; if (it1->b==l.b){ if (it1->a<=l.a){ s.erase(it1); continue; } return; } double x=xinter(*it1,*it2); if (yinter(l,x)<yinter(*it1,x)-eps) break; s.erase(it1); } while (true){ set<line>::iterator it1=s.upper_bound(l); if (it1==s.begin()) break; --it1; if (it1==s.begin()) break; set<line>::iterator it2=it1;--it2; if (it1->b==l.b){ if (it1->a<=l.a){ s.erase(it1); continue; } return; } double x=xinter(*it1,*it2); if (yinter(l,x)<yinter(*it1,x)-eps) break; s.erase(it1); } set<line>::iterator it1=s.lower_bound(l); if (it1!=s.end() && it1!=s.begin()){ set<line>::iterator it2=it1;--it2; double x=xinter(*it1,*it2); if (yinter(l,x)<=yinter(*it1,x)+eps) return; } s.insert(l); if (s.size()==1){ last_line=l; last_x=-1e12; } else if (s.find(last_line)==s.end()) last_line=l; else if (yinter(last_line,last_x)<yinter(l,last_x)) last_line=l; } int n; test t[50000]; double x[50000],min_one[50000],max_one[50000]; int main(){ fscanf(fin,"%d",&n); for (int i=0;i<n;++i) fscanf(fin,"%d%d",&t[i].a,&t[i].b); sort(t,t+n); { int suma=0,sumb=0; for (int i=0;i<n;++i){ suma+=t[n-i-1].a; sumb+=t[n-i-1].b; x[n-i-1]=double(suma)/double(sumb); } } { reset(); for (int i=1;i<n;++i){ insert(line(t[i-1].a,-t[i-1].b)); max_one[i]=best(x[i]); } } { reset(); for (int i=n-1;i>=1;--i){ insert(line(-t[i].a,-t[i].b)); min_one[i]=-best(-x[i]); } } int cou=0; for (int i=1;i<n;++i) if (min_one[i]<max_one[i]-eps) ++cou; fprintf(fout,"%d\n",cou); for (int i=1;i<n;++i) if (min_one[i]<max_one[i]-eps) fprintf(fout,"%d\n",i); return 0; } There exist a much simpler alternatives. One way is to divide the list in half, construct the hull for the lower half and query the score of every point from the higher half on the lower part in linear time. This would handle all the queries across the division point, which means we could recurse on each half to get to a O(nlogn) algorithm. The other, much more elegant way by Bruce Merry is to consider what happens when we increment D and thus have a new point in our candidate set. Everything to the right (i.e. with higher T) can be discarded from the bag, because M will be (and remain) higher than the current test, and any tests to the right will be both of lower percentage and greater weight than the current test. Furthermore, if three elements in the bag are convex, then the middle one can never be optimal and it be discarded from the bag. This becomes a typical convex hull maintenance problem and can be done in O(N) time after the sorting. Bruce's code is here: #include <fstream> #include <algorithm> #include <complex> #include <vector> #include <iterator> #include <numeric> using namespace std; #define MAXN 50000 typedef long long ll; typedef complex<ll> point; static ll cross(const point &a, const point &b) { return imag(conj(a) * b); } static ll area2(const point &a, const point &b, const point &c) { return cross(b - a, c - a); } struct compare_slope { bool operator()(const point &a, const point &b) { return area2(point(0, 0), a, b) > 0; } }; int main() { static point points[MAXN]; static point worst_in[MAXN]; static point hull[MAXN]; point total, slope; int N, H; vector<int> ans; ifstream in("schul.in"); ofstream out("schul.out"); in >> N; for (int i = 0; i < N; i++) { int p, t; in >> p >> t; points[i] = point(t, p); } sort(points, points + N, compare_slope()); total = accumulate(points, points + N, point(0, 0)); H = 0; slope = point(0, 0); for (int i = N - 1; i > 0; i--) { while (H && imag(hull[H - 1]) <= imag(points[i])) H--; while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i]) >= 0) H--; hull[H++] = points[i]; slope += points[i]; while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1]) <= 0) H--; worst_in[i - 1] = hull[H - 1]; } H = 0; slope = total; for (int i = 0; i < N - 1; i++) { while (H && real(hull[H - 1]) >= real(points[i])) H--; while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i]) >= 0) H--; hull[H++] = points[i]; slope -= points[i]; while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1]) >= 0) H--; point best_out = hull[H - 1]; if (cross(slope, worst_in[i] - best_out) < 0) ans.push_back(i + 1); } out << ans.size() << "\n"; copy(ans.begin(), ans.end(), ostream_iterator<int>(out, "\n")); return 0; }

schul – ლუკა მაჭარაძის თარგმანი

ივარაუდეთ გარკვეული D მნიშვნელობისთვის, მასწავლებლის არჩევანი პროპორციულია M–ის და ბესის სურს, რომ ეს პროპორციულობა გაზარდოს. თუ იგი ყოველ ტესტს როგორც M-ს მიმატებული ან გამოკლებული რაიმე რომელიმე ნიშნის რიცხვი(და არა პროცენტი), მაშინ მას ენდომება, რომ დაიყვანოს მისი ქულა მინიმალურ რიცხვამდე, რომელიც მეტია M-ზე და დაიტოვოს ის ნიშნები, რომლებიც M-ზე ნაკლებია. თუ მოხდება ისე, რომ მასწავლებლის არჩევანი განსხვავებულია მაშინ მას შეუძლია რომ შეცვალოს ტესტი რათა მიიღოს 0–ზე მეტი და M–ზე ნაკლები რაც გააუმჯობესებს მის ქულას. პირველი მცდელობა იქნება იმისა, რომ გამოვარკვიოთ დამოუკიდებლად ყოველი D-სთვის. გაარკვიეთ მასწავლებლის მიერ დალაგებული ქულები და მოძებნეთ ყველაზე ცუდი ტესტი იმ ტესტებიდან რომელიცც მასწავლებელმა აირჩია და საუკეთესო ნაწერი ტესტებიდან რომელებიც "გადაგდებულია" მასწავლებლის მიერ. თუ ერთის შეცვლა მეორეთი აუმჯობესებს ბესის ქულას მაშინ შეინახეთ D-ს მნიშვნელობა. ეს მოგცემთ O(N^2) ამოხსნას. ცოტა მონაწილემ სცადა რომ ევრისტიკა ჩაემატებინათ თავიანთ კოდში, რათა რანთაიმი გაეუმჯობესებინათ. აქედან უმეტესობა ამყარებდა იმედს დასკვნაზე, ამონახსნი წერტილების და ადგილმდებარეობების( სადაც მინ და მაქს ჩნდება) სიმკვრივის შესახებ. რთული იყო მონაცემთა კონსტრუირება ისე რომ ევრისტიკაზე დაეფუძნებინოთ ზედა და ქვედა ზღვარი ასე რომ ორი მონაწილე კვლავ ცდილობს მიიღოს ევრისტიკული ამოხსნა. ევრისტიკა: ეკონომიკური მოვლენებისა და პროცესების ანალიზის მეთოდი, გადაწყვეტილების მიღება, რომელიც დაფუძნებულია ინტუიციაზე, საზრიანობაზე, ანალოგიებზე, გამოცდილებაზე, გამომგონებლობაზე, რაც უნდა ეყრდნობოდეს ადამიანის ტვინის განსაკუთრებულ თვისებებსა დაადამიანის უნარს გადაწყვიტოს ამოცანები, რომლებისთვისაც ფორმალური მათემატიკური ალგორითმი, გადაწყვეტის წესი უცნობია. რამდენიმე გზა არსებობს O(nlogn) ამოხსნამდეშეამჩნიეთ რომ პრობლემა დადის მაქსიმუმის და მინიმუმის პოვნამდე წრფივი კომბინაციის ორი ცვლადის. მინიმუმი არის მაქციმუმის სარკისებური ექვივალენტი იქსი ან კვეთს ან კუთხეებს ცარიელზე ან იმ ადგილს სადაც ხაზი კვეთს ვერტიკალურ ხაზს ფიქსირებული იქსის მნიშვნელობით. ორივე შემთხვევაში თუ წერტილი არის ჩაზნექილი თავის ორ მეზობელთან ის წაიშლება. ორივე მეთოდი იხსნება O(nlogn) დროში ორობითი ხის გამოყენებით. ეს შეიძლება აიხსნას პროფესორიBrian Dean-ის ანიმაციური შენიშვნებით რომელიც შეგიძლიათ იხილოთ ამ მისამართზე: http://www.cs.clemson.edu/~bcdean/cowschool.swf ეს არის ერთადერთი ტიპის O(nlogn)დროში გადაწყვეტილი ამოხსნა ამ კონკურსზე. ბოდიში ყველა Pascal-ის პროგრამისტებთან, STL კომპლექტი იძლევს უზარმაზარ უპირატესობას C++ პროგრამისტებს.Nima Ahmadi Pour ირანიდან იყო ერთადერთი კონკურსანტი ვინც ამოხსნა სწორად ეს ამოცანა(ასევე Adrian Kuegel-ი იყო ძალიან ახლოს ამოხსნასთან). ეს კი Nima-ს კოდი : #include <cstdlib> #include <cstdio> #include <algorithm> #include <set> #include <utility> using namespace std; double eps=1e-8; FILE *fin=fopen("schul.in","r"); FILE *fout=fopen("schul.out","w"); struct test{ int a,b; test(){} test(int t1,int t2):a(t1),b(t2){} }; bool operator<(const test& t1,const test& t2){ return t1.a*t2.b<t2.a*t1.b; } struct line{ int a,b; line(){} line(int t1,int t2):a(t1),b(t2){} }; bool operator<(const line& l1,const line& l2){ return l1.b<l2.b; } set<line> s; line last_line; double last_x; void reset(){ s.clear(); } double xinter(const line& l1,const line& l2){ return double(l1.a-l2.a)/double(l2.b-l1.b); } double yinter(const line& l1,double x){ return l1.b*x+l1.a; } double best(double x){ double ans=-1e12; set<line>::iterator it=s.find(last_line); while (it!=s.end() && yinter(*it,x)>ans){ ans=yinter(*it,x); ++it; } --it; last_x=x; last_line=*it; return ans; } void insert(const line& l){ while (true){ set<line>::iterator it1=s.lower_bound(l); if (it1==s.end()) break; set<line>::iterator it2=it1;++it2; if (it2==s.end()) break; if (it1->b==l.b){ if (it1->a<=l.a){ s.erase(it1); continue; } return; } double x=xinter(*it1,*it2); if (yinter(l,x)<yinter(*it1,x)-eps) break; s.erase(it1); } while (true){ set<line>::iterator it1=s.upper_bound(l); if (it1==s.begin()) break; --it1; if (it1==s.begin()) break; set<line>::iterator it2=it1; --it2; if (it1->b==l.b){ if (it1->a<=l.a){ s.erase(it1); continue; } return; } double x=xinter(*it1,*it2); if (yinter(l,x)<yinter(*it1,x)-eps) break; s.erase(it1); } set<line>::iterator it1=s.lower_bound(l); if (it1!=s.end() && it1!=s.begin()){ set<line>::iterator it2=it1; --it2; double x=xinter(*it1,*it2); if (yinter(l,x)<=yinter(*it1,x)+eps) return; } s.insert(l); if (s.size()==1){ last_line=l; last_x=-1e12; } else if (s.find(last_line)==s.end()) last_line=l; else if (yinter(last_line,last_x)<yinter(l,last_x)) last_line=l; } int n; test t[50000]; double x[50000],min_one[50000],max_one[50000]; int main(){ fscanf(fin,"%d",&n); for (int i=0;i<n;++i) fscanf(fin,"%d%d",&t[i].a,&t[i].b); sort(t,t+n); { int suma=0,sumb=0; for (int i=0;i<n;++i){ suma+=t[n-i-1].a; sumb+=t[n-i-1].b; x[n-i-1]=double(suma)/double(sumb); } } { reset(); for (int i=1;i<n;++i){ insert(line(t[i-1].a,-t[i-1].b)); max_one[i]=best(x[i]); } } { reset(); for (int i=n-1;i>=1;--i){ insert(line(-t[i].a,-t[i].b)); min_one[i]=-best(-x[i]); } } int cou=0; for (int i=1;i<n;++i) if (min_one[i]<max_one[i]-eps) ++cou; fprintf(fout,"%d\n",cou); for (int i=1;i<n;++i) if (min_one[i]<max_one[i]-eps) fprintf(fout,"%d\n",i); return 0; } ასევე არსებობს უფრო მარტივი ალტერნატივები. ერთი გზა არის რომ გავყოთ ლისტი ნახევრად.შექვქმნათ hull ქვედა ნახევრისთვის და query რაოდენობა ყოველი წერტილისთვის ზედა ნახვერიდან ქვედა ნახევრისკენ წრფივ დროში. ეს მოაშორებს ყველა queries მთელ გაყოფილ წერტილებზე, რაც მოგვცემს რეკურსიის საშალებას ორივე ნახევრამდე რათა გამოვიყენოთ O(nlogn) ალგორითმი. მეორე უფრო ელეგანტური გზა რომელიც ეკუთვნის Bruce Merry-ს არის ის რომ გავითვალისწინოთ თუ რა მოხდება როდესაც იზრდება D და ამასთანავე გვაქვს ახალი წერტილი ჩვენი კანდიდატურისთვის. ყველა მარჯვენა(ანუ T-ზე მაღალი) შეიძლება რომ მოვიშოროთ, რადგანაც M იქნება იგივე და უფრო მაღალი ვიდრე კონკრეტული ტესტი და ასევე ნებისმიერი ტესტი მარჯვნივ იქნება როგორც დაბალი პროცენტულად ასევე უფრო მეტი წონა ექნებ ვიდრე კონკრეტულს ტესტს. ასევე თუ გვაქვს სამი ელემენტი არისამოზნექილი, მაშინ შუაში მყოფი ვერასდროს იქნება ოპტიმალური და მას მოვიცილებთ. ეს ხდება ტიპური convex hull maintenance პრობლემა და შეიძლება გადაიჭრას O(N) დროში სორტირების შემდეგ. Bruce-ს კოდი იხილეთ აქ: #include <fstream> #include <algorithm> #include <complex> #include <vector> #include <iterator> #include <numeric> using namespace std; #define MAXN 50000 typedef long long ll; typedef complex<ll> point; static ll cross(const point &a, const point &b) { return imag(conj(a) * b); } static ll area2(const point &a, const point &b, const point &c) { return cross(b - a, c - a); } struct compare_slope { bool operator()(const point &a, const point &b) { return area2(point(0, 0), a, b) > 0; } }; int main() { static point points[MAXN]; static point worst_in[MAXN]; static point hull[MAXN]; point total, slope; int N, H; vector<int> ans; ifstream in("schul.in"); ofstream out("schul.out"); in >> N; for (int i = 0; i < N; i++) { int p, t; in >> p >> t; points[i] = point(t, p); } sort(points, points + N, compare_slope()); total = accumulate(points, points + N, point(0, 0)); H = 0; slope = point(0, 0); for (int i = N - 1; i > 0; i--) { while (H && imag(hull[H - 1]) <= imag(points[i])) H--; while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i])> = 0) H--; hull[H++] = points[i]; slope += points[i]; while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1])< = 0) H--; worst_in[i - 1] = hull[H - 1]; } H = 0; slope = total; for (int i = 0; i < N - 1; i++) { while (H && real(hull[H - 1]) >= real(points[i])) H--; while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i])> = 0) H--; hull[H++] = points[i]; slope -= points[i]; while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1])> = 0) H--; point best_out = hull[H - 1]; if (cross(slope, worst_in[i] - best_out) < 0) ans.push_back(i + 1); } out << ans.size() << "\n"; copy(ans.begin(), ans.end(), ostream_iterator<int>(out, "\n")); return 0; }

Nima Ahmadi Pour from Iran was the only person to implement one correctly

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
double eps=1e-8;
FILE *fin=fopen("schul.in","r");
FILE *fout=fopen("schul.out","w");
struct test{
       int a,b;
       test(){}
       test(int t1,int t2):a(t1),b(t2){}
};
bool operator<(const test& t1,const test& t2){
       return t1.a*t2.b<t2.a*t1.b;
}
struct line{
       int a,b;
       line(){}
       line(int t1,int t2):a(t1),b(t2){}
};
bool operator<(const line& l1,const line& l2){
       return l1.b<l2.b;
}
set<line> s;
line last_line;
double last_x;
void reset(){
       s.clear();
}
double xinter(const line& l1,const line& l2){
       return double(l1.a-l2.a)/double(l2.b-l1.b);
}
double yinter(const line& l1,double x){
       return l1.b*x+l1.a;
}
double best(double x){
       double ans=-1e12;
       set<line>::iterator it=s.find(last_line);
       while (it!=s.end() && yinter(*it,x)>ans){
               ans=yinter(*it,x);
               ++it;
       }
       --it;
       last_x=x;
       last_line=*it;
       return ans;
}
void insert(const line& l){
       while (true){
               set<line>::iterator it1=s.lower_bound(l);
               if (it1==s.end())
                       break;
               set<line>::iterator it2=it1;++it2;
               if (it2==s.end())
                       break;
               if (it1->b==l.b){
                       if (it1->a<=l.a){
                               s.erase(it1);
                               continue;
                       }
                       return;
               }
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<yinter(*it1,x)-eps)
                       break;
               s.erase(it1);
       }
       while (true){
               set<line>::iterator it1=s.upper_bound(l);
               if (it1==s.begin())
                       break;
               --it1;
               if (it1==s.begin())
                       break;
               set<line>::iterator it2=it1;--it2;
               if (it1->b==l.b){
                       if (it1->a<=l.a){
                               s.erase(it1);
                               continue;
                       }
                       return;
               }
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<yinter(*it1,x)-eps)
                       break;
               s.erase(it1);
       }
       set<line>::iterator it1=s.lower_bound(l);
       if (it1!=s.end() && it1!=s.begin()){
               set<line>::iterator it2=it1;--it2;
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<=yinter(*it1,x)+eps)
                       return;
       }
       s.insert(l);
       if (s.size()==1){
               last_line=l;
               last_x=-1e12;
       }
       else if (s.find(last_line)==s.end())
               last_line=l;
       else if (yinter(last_line,last_x)<yinter(l,last_x))
               last_line=l;
}
int n;
test t[50000];
double x[50000],min_one[50000],max_one[50000];
int main(){
       fscanf(fin,"%d",&n);
       for (int i=0;i<n;++i)
               fscanf(fin,"%d%d",&t[i].a,&t[i].b);
       sort(t,t+n);
       {
               int suma=0,sumb=0;
               for (int i=0;i<n;++i){
                       suma+=t[n-i-1].a;
                       sumb+=t[n-i-1].b;
                       x[n-i-1]=double(suma)/double(sumb);
               }
       }
       {
               reset();
               for (int i=1;i<n;++i){
                       insert(line(t[i-1].a,-t[i-1].b));
                       max_one[i]=best(x[i]);
               }
       }
       {
               reset();
               for (int i=n-1;i>=1;--i){
                       insert(line(-t[i].a,-t[i].b));
                       min_one[i]=-best(-x[i]);
               }
       }
       int cou=0;
       for (int i=1;i<n;++i)
               if (min_one[i]<max_one[i]-eps)
                       ++cou;
       fprintf(fout,"%d\n",cou);
       for (int i=1;i<n;++i)
               if (min_one[i]<max_one[i]-eps)
                       fprintf(fout,"%d\n",i);
       return 0;
}

Bruce's code is here

#include <fstream>
#include <algorithm>
#include <complex>
#include <vector>
#include <iterator>
#include <numeric>

using namespace std;

#define MAXN 50000

typedef long long ll;
typedef complex<ll> point;

static ll cross(const point &a, const point &b) { return imag(conj(a) *
b); }
static ll area2(const point &a, const point &b, const point &c)
{ return cross(b - a, c - a); }

struct compare_slope
{
    bool operator()(const point &a, const point &b)
    { return area2(point(0, 0), a, b) > 0; }
};

int main()
{
    static point points[MAXN];
    static point worst_in[MAXN];
    static point hull[MAXN];
    point total, slope;
    int N, H;
    vector<int> ans;
    ifstream in("schul.in");
    ofstream out("schul.out");

    in >> N;
    for (int i = 0; i < N; i++)
    {
        int p, t;
        in >> p >> t;
        points[i] = point(t, p);
    }
    sort(points, points + N, compare_slope());
    total = accumulate(points, points + N, point(0, 0));

    H = 0;
    slope = point(0, 0);
    for (int i = N - 1; i > 0; i--)
    {
        while (H && imag(hull[H - 1]) <= imag(points[i]))
            H--;
        while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i])
>= 0)
            H--;
        hull[H++] = points[i];
        slope += points[i];
        while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1])
<= 0)
            H--;
        worst_in[i - 1] = hull[H - 1];
    }

    H = 0;
    slope = total;
    for (int i = 0; i < N - 1; i++)
    {
        while (H && real(hull[H - 1]) >= real(points[i]))
            H--;
        while (H >= 2 && area2(hull[H - 2], hull[H - 1], points[i])
>= 0)
            H--;
        hull[H++] = points[i];
        slope -= points[i];
        while (H >= 2 && cross(slope, hull[H - 2] - hull[H - 1])
>= 0)
            H--;
        point best_out = hull[H - 1];
        if (cross(slope, worst_in[i] - best_out) < 0)
            ans.push_back(i + 1);
    }

    out << ans.size() << "\n";
    copy(ans.begin(), ans.end(), ostream_iterator<int>(out, "\n"));
    return 0;
}