#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int n=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
int n,m;
int x[10005],y[10005],a[10005],b[10005];
struct Point{
int x,y;
};
int cross(Point x,Point y,Point z){
y.x-=x.x,y.y-=x.y;
z.x-=x.x,z.y-=x.y;
return z.y*y.x-z.x*y.y;
}
int f[205];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int rx=(1ll<<60),ry;
int ans=(1ll<<60);
vector<pair<int,int>> lnk;
Point get(int c,int d){
vector<array<int,4>> v;
for(int i=1;i<=m;i++){
v.push_back({a[i]*c+b[i]*d,x[i],y[i],i});
}
sort(v.begin(),v.end());
for(int i=1;i<=n;i++)f[i]=i;
Point res=(Point){0,0};
vector<pair<int,int>> pp;
for(auto it:v){
if(find(it[1])!=find(it[2])){
f[find(it[1])]=find(it[2]);
pp.push_back({it[1],it[2]});
res.x+=a[it[3]],res.y+=b[it[3]];
}
}
//cout<<"Q"<<res.x<<" "<<res.y<<"\n";
if(res.x*res.y<ans){
lnk=pp;
ans=res.x*res.y,rx=res.x,ry=res.y;
}
else if(res.x*res.y==ans&&res.x<rx)lnk=pp,rx=res.x,ry=res.y;
return res;
}
map<pair<int,int>,int> mp;
void findhull(Point a,Point b){
//¼ÙÉè a.x<b.x
//³¢ÊÔÕÒµ½Ò»¸öµã p ʹ p ÔÚ a,b ÓÒ±ß
//¼´ cross(a,b,p)<0
//¼´ b.x-a.x b.y-a.y
//(p.y-a.y)*(b.x-a.x)-(b.y-a.y)*(p.x-a.x)<0
//¹Ê½«±ßȨÉèÖÃΪ (b.x-a.x)*b[i]+(a.y-b.y)*a[i], ÕÒ×îСÉú³ÉÊ÷.
Point p=get(a.y-b.y,b.x-a.x);
if(mp.count({p.x,p.y}))return;
mp[{p.x,p.y}]=1;
if(cross(a,b,p)<0){
findhull(a,p),findhull(p,b);
}
else return;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
x[i]=read(),y[i]=read(),a[i]=read(),b[i]=read();
x[i]++,y[i]++;
}
Point x1=get(1,0),x2=get(0,1);
assert((x1.x<=x2.x));
findhull(x1,x2);
cout<<rx<<" "<<ry<<"\n";
for(auto v:lnk)cout<<v.first-1<<" "<<v.second-1<<"\n";
return 0;
}
//447324718
//447,341,898
//21974 20357
//21778 20541
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
